丁雪晶

摘要：針對《C語言程序設(shè)計(jì)》課程，在教學(xué)過程中遞歸函數(shù)部分普遍反映比較難，文章給出了遞歸函數(shù)的定義和設(shè)計(jì)思路，并通過對幾大典型的遞歸問題給出求解思路和參考代碼，加強(qiáng)學(xué)生對遞歸函數(shù)的理解，提高學(xué)生對遞歸函數(shù)的掌握和應(yīng)用。

關(guān)鍵詞：C語言；遞歸函數(shù)；教學(xué)設(shè)計(jì)；案例分析

中國分類號：G424 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）16-0150-03

1引言

《C語言程序設(shè)計(jì)》是高等學(xué)校計(jì)算機(jī)及相關(guān)專業(yè)的必修課，其以短小精悍、使用靈活、功能強(qiáng)大等特點(diǎn)深受人們的喜愛。函數(shù)作為C語言程序設(shè)計(jì)的基本組成單位，在教學(xué)過程中占據(jù)著非常重要的地位，而遞歸函數(shù)的設(shè)計(jì)則是函數(shù)教學(xué)中的重點(diǎn)和難點(diǎn)。

2遞歸函數(shù)概述

在編程語言中，函數(shù)直接或間接調(diào)用函數(shù)本身，該函數(shù)稱為遞歸函數(shù)[1]。但遞歸也并不是簡單的“自己調(diào)用自己”。遞歸算法的思想是：把要解決的問題分解成與原問題有相同解法，且規(guī)模較小的問題，直到遇見終止條件。

所以一般情況下，能采用遞歸函數(shù)來解決的問題，需滿足以下兩個(gè)條件：

（1）該問題可以縮小規(guī)模，且縮小后的問題與原問題有相同的解法；

（2）必定要有一個(gè)明確的結(jié)束遞歸的條件。

為了方便理解，以求n！為例，這是一個(gè)明顯的可以用遞歸解決的問題：

n！可以表示為：[n！=n×n-1×n-2…×2×1=n×n-1！]

即有：

[n！=1 n=1n×n-1！ n>1 ]

或者

[f（n）=1 n=1n×f（n） n>1 ]

首先看看該問題是否滿足遞歸的兩個(gè)條件的：

當(dāng)n>=2，求f（n）只需求出f（n-1），也就是說求n的階乘問題，轉(zhuǎn)化成了規(guī)模更小的求n-1階乘問題；

而遞歸結(jié)束條件為，n=1時(shí)， fun（1） = 1。

因此，我們可以很容易的寫出計(jì)算n！的遞歸程序：

int fac（int n）

{

if（n==1）

return 1；

else

return n*fac（n-1）；

}

在編寫遞歸函數(shù)時(shí)，通常把判斷遞歸結(jié)束的條件寫在前面，以確保函數(shù)在遇到結(jié)束條件時(shí)能中止遞歸，否則會(huì)導(dǎo)致程序死循環(huán)。

3 典型案例分析

例1：求Fibonacci數(shù)列（斐波那契）的第n項(xiàng)值，表示如下：

[fibn=1 ，n=0或 n=1fibn-1+fibn-2， n>1]

此例將求規(guī)模為n的問題轉(zhuǎn)化為規(guī)模較小的n-1和n-2問題，而遞歸結(jié)束條件為，一直轉(zhuǎn)化到規(guī)模為1和0時(shí)。所以遞歸函數(shù)設(shè)計(jì)如下：

int fib（int n）

{

if（n==1 || n==2）

return 1；

else

return fib（n-1）+fib（n-2）；

}

void main（）

{

int num=fib（8）；

printf（"%d"，num）；

}

輸出結(jié)果：21

例2：漢諾塔問題[1]：有三根桿子A，B，C。A桿上有若干盤子，把所有盤子從A桿移到C桿（可借助B桿）。規(guī)則是：每次只能移動(dòng)一個(gè)盤子，且在移動(dòng)過程中三根桿上都始終保持大盤在下，如圖1所示。求移動(dòng)的步驟和移動(dòng)的次數(shù)。

實(shí)現(xiàn)這個(gè)漢諾塔問題的遞歸算法可以有如下步驟（n表示盤的個(gè)數(shù)，從上往下依次為第1個(gè)，第2個(gè)…第n個(gè)）：

當(dāng)n=1時(shí)，即只有一個(gè)盤子，為遞歸算法的結(jié)束條件，從A盤移到C盤即可；

當(dāng)n>=2時(shí)：

（1）先將A柱上面的n-1個(gè)盤子從A柱借助C柱，移到B柱；

（2）將A柱的第n個(gè)盤子從A柱移動(dòng)C柱；

（3）再將B柱的n-1個(gè)盤子借助A柱，移到C柱。

將漢諾塔的規(guī)模為n的問題轉(zhuǎn)化為規(guī)模小一點(diǎn)的n-1問題，通過遞歸會(huì)將規(guī)模繼續(xù)減小，直到遇到結(jié)束條件的規(guī)模為1的問題。

遞歸算法hanoi實(shí)現(xiàn)如下：

#include

int num=0；

void hanoi（intn，charA，charB，char C）//將n個(gè)盤子從A柱，借助B柱，移動(dòng)C柱

{

if（n==1）//結(jié)束條件

{

num++；

printf（"第%d次：%d號盤：%c——>%c＼n"，num，n，A，C）；

}

else

{

hanoi（n-1，A，C，B）； //n-1個(gè)盤子從A柱借助C柱，移到B柱

num++；

printf（"第%d次：%d號盤：%c——>%c＼n"，num，n，A，C）；

hanoi（n-1，B，A，C）；//n-1個(gè)盤子從B柱借助A柱，移到C柱

}

}

void main（）

{

hanoi（3，'A'，'B'，'C'）；//將3個(gè)盤子從A移到C

}

實(shí)驗(yàn)結(jié)果如圖2所示：

例3：八皇后問題[2]

八皇后問題是一個(gè)以國際象棋問題：如何在8×8的棋盤上擺8個(gè)皇后，每行每列只能擺一個(gè)皇后，使得這8個(gè)皇后無法相互攻擊，即任意的2個(gè)皇后不能在同一行、同一列或?qū)蔷€上，如圖3所示。當(dāng)然這是八皇后問題的初始規(guī)則，現(xiàn)在可以將其推廣為四皇后，五皇后等n皇后問題，此處的n須等于1或大于等于4，問題才有解。

解題思路：

從第一行開始擺放皇后，每擺放1行，遞歸一次，每次遞歸里面考慮8列， 即對每一行皇后有8個(gè)可能的位置可以放。找到一個(gè)與前面行的皇后都不會(huì)互相攻擊的位置，然后再遞歸進(jìn)入下一行。

在這里用一個(gè)一維數(shù)組來表示相應(yīng)行對應(yīng)的列，即k[i]=j表示，第i行的皇后放在第j列?；屎螽a(chǎn)生沖突的條件有3個(gè)：同行、同列、對角線。例如對于m行和n行擺放皇后時(shí)的沖突：同列：k[m]=k[n]。對角線有主對角線方向和副對角線方向。主對角線滿足，兩個(gè)皇后的行之差等于他們的列之差：m-n=k[m]-k[n]； 副對角線方向， 兩個(gè)皇后的行之差等于其列之差的相反數(shù)：m-n=k[n]-k[m]。 只有當(dāng)前皇后和前面所有已擺好的皇后都不會(huì)產(chǎn)生沖突時(shí)，才能進(jìn)行下一個(gè)皇后的擺放，即下一級遞歸。

遞歸函數(shù)設(shè)計(jì)如下：

#include

intk[4]， n=4， num=0； //n設(shè)為4，即4行4列

void print（）{ //輸出皇后矩陣，擺了皇后輸出1，沒擺皇后輸出0

for（int i=0； i

for（int j=0； j

if（k[i]==j）

printf（"1 "）；

else

printf（"0 "）；

printf（"＼n"）；

}

printf（"＼n"）；

}

voidfun（int r）{

int flag=0；

if（r == n）{//當(dāng)擺完最后一行時(shí)，輸出皇后矩陣，遞歸結(jié)束條件

print（）；

num++；

return；

}

for（int i=0； i

k[r] = i；//第r行的皇后位置放在i列

flag=1；

for（int j=0； j

if（k[r]==k[j] || r-j==k[r]-k[j] || r-j==k[j]-k[r]）{//產(chǎn)生沖突的條件

flag=0；

break；

}

if（flag）

fun（r+1）； //進(jìn)入下一級遞歸，即擺放第r+1個(gè)皇后

}

}

void main（）{

fun（0）；

printf（"共%d種擺放＼n"，num）；

}

實(shí)驗(yàn)結(jié)果如圖4所示：

例4：二叉樹的遍歷[3]

一棵二叉樹由根結(jié)點(diǎn)、左子樹和右子樹三部分組成，因而只要依次遍歷這三個(gè)部分，就能遍歷整棵二叉樹的所有結(jié)點(diǎn)。遍歷方式有先序遍歷（先根結(jié)點(diǎn)，然后。左子樹右子樹）、中序遍歷（先左子樹，然后根結(jié)點(diǎn)，最后右子樹）、后序遍歷（先左子樹、右子樹，然后根結(jié)點(diǎn)），這三種遍歷算法采用遞歸方式比非遞歸方式要簡單得多：

//先序遍歷

void PreOrder（BiTreebt） //bt為二叉樹或某一子樹根節(jié)點(diǎn)的指針

{

if（bt！=NULL） //如果bt為空，遞歸結(jié)束

{

visit（bt）；//訪問根節(jié)點(diǎn)

PreOrder（bt->lchild）； //先序遍歷左子樹

PreOrder（bt->rchild）； //先序遍歷右子樹

}

}

//中序遍歷

void InOrder（BiTreebt） //bt為二叉樹或某一子樹根節(jié)點(diǎn)的指針

{

if（bt！=NULL） //如果bt為空，遞歸結(jié)束

{

InOrder（bt->lchild）； //先序遍歷左子樹

visit（bt）；//訪問根節(jié)點(diǎn)

InOrder（bt->rchild）； //先序遍歷右子樹

}

}

//后序遍歷

void PostOrder（BiTreebt） //bt為二叉樹或某一子樹根節(jié)點(diǎn)的指針

{

if（bt！=NULL） //如果bt為空，遞歸結(jié)束

{

PostOrder（bt->lchild）； //先序遍歷左子樹

PostOrder（bt->rchild）； //先序遍歷右子樹

visit（bt）；//訪問根節(jié)點(diǎn)

}

}

由此可見，采用遞歸方式，三種遍歷算法的區(qū)別只在于訪問根節(jié)點(diǎn)語句的位置不同，相比非遞歸算法要簡單很多。

4結(jié)論

在C語言教學(xué)中，遞歸函數(shù)的設(shè)計(jì)一直是其中的重點(diǎn)和難點(diǎn)，本文首選分析了采用遞歸算法解決問題的基本條件，然后列舉了幾個(gè)比較經(jīng)典的案例，對其進(jìn)行分析執(zhí)行，使學(xué)生能正確掌握遞歸函數(shù)的設(shè)計(jì)。

參考文獻(xiàn)：

[1]潭浩強(qiáng).C語言程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2017.

[2]樊艷芬，周琪云，吳帥.用Java語言實(shí)現(xiàn)八皇后問題的遞歸和非遞歸算法設(shè)計(jì)[J].計(jì)算機(jī)與現(xiàn)代化，2007（3）.

[3]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2013.