C語言中遞歸函數(shù)的應(yīng)用

史春水

摘要：該文對C語言遞歸函數(shù)的定義及調(diào)用進(jìn)行了分析，就遞歸函數(shù)的應(yīng)用以例題的形式進(jìn)行了詳細(xì)的講解，便于初學(xué)者掌握遞歸函數(shù)分析思路與方法。

關(guān)鍵詞：C語言；遞歸函數(shù)；遞歸調(diào)用；遞歸應(yīng)用

中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）28-0271-02

1 遞歸函數(shù)定義

在結(jié)構(gòu)化程序設(shè)計(jì)中，一個(gè)函數(shù)在其定義中直接或間接地調(diào)用該函數(shù)本身的一種方法。在函數(shù)中直接調(diào)用函數(shù)本身，稱為直接遞歸調(diào)用，如下圖1所示。在函數(shù)中調(diào)用其他函數(shù)，其他函數(shù)又調(diào)用原函數(shù)，就構(gòu)成了函數(shù)自身的間接調(diào)用，稱為間接遞歸，如下圖2所示：

2 遞歸函數(shù)的幾個(gè)注意事項(xiàng)

（1）為求解規(guī)模為n的問題，設(shè)法將它分解成規(guī)模較小的問題，每次減少一個(gè)或幾個(gè)元素，然后從這些較小的問題解進(jìn)一步分解成另一個(gè)更少問題的解，并且這些規(guī)模較小的問題同樣采用的相同的分解方法，分解成規(guī)模更小的問題，直到規(guī)模N=1或0時(shí)，能直接求解。

（2）遞歸算法：遞歸=遞推+回歸，分兩個(gè)階段。在遞推階段，把規(guī)模為n的問題求解化解為規(guī)模小于n的問題求解，依次減少一個(gè)或幾個(gè)元素，直到規(guī)模N=1或0時(shí)，能直接求解。然后回歸，推出n=2時(shí)解，推出n=3時(shí)解，........直到n的解。

（3）遞歸算法必需要有一個(gè)明確的出口。

（4）一般來說，遞歸需要三條件有：遞歸出口、有條件的遞歸前進(jìn)段和同條件的遞歸返回段。

3 遞歸函數(shù)的幾個(gè)典型應(yīng)用

（1）應(yīng)用一：求和問題

求1+2+3+4+5+6+.........+N的值。

分析：設(shè)sum（n）為前n項(xiàng)的和，則sum（n-1）為前n-1項(xiàng)的和，則有sum（n）=sum（n-1）+n；也就是說要求前n項(xiàng)的和，只要求前n-1項(xiàng)的和再加上n的值，求前n-1項(xiàng)的和只要求前n-2項(xiàng)的和再加上n-1的值，依次類推，直到n=1時(shí)，sum（n）=1，這就是遞歸函數(shù)出口，然后回歸求sum（2）=sum（1）+2，依次類推求sum（n）；

源程序如下：

#include

int sum（int n）

{int t；

if（n==1） t=1；

else t=sum（n-1）+n；

return t；

}

main（）

{int n；

printf（“please input a number＼n”，&n;）；

printf（“1+2+3+4+.....+n=%d”，sum（n））；

getchar（）；

}

（2）應(yīng)用二：猴子摘桃子問題

有一群猴子，去摘了一堆桃子，商量之后決定每天吃剩余桃子的一半，當(dāng)每天大家吃完桃子之后，有個(gè)貪心的小猴都會偷偷再吃一個(gè)桃子，按照這樣的方式猴子們每天都快樂地吃著桃子，直到第十天，當(dāng)大家再想吃桃子時(shí)，發(fā)現(xiàn)只剩下一個(gè)桃子了，問：猴子們一共摘了多少桃子？

分析：設(shè)x1為前一天桃子數(shù)，設(shè)x2為第二天桃子數(shù)，則

x2=x1/2-1，變型為 x1=（x2+1）*2

x3=x2/2-1， 變型為x2=（x3+1）*2

以此類推： x前=（x后+1）*2 ；

源程序如下：

#include

int get（n）

{ int num； //定義所剩桃子數(shù)

if（n==10）

{return 1；

}

else

num = get（（n+1）+1）*2；

printf（"第%d天所剩桃子%d個(gè)＼n"， n， num）； //天數(shù)，所剩桃子個(gè)數(shù)

}

return num；

}

main（）

{ int num = get（1）；

printf（"猴子第一天摘了：%d個(gè)桃子。＼n"， num）；

getchar（）；

}

（3）應(yīng)用三：求2個(gè)數(shù)的最大公約數(shù)問題

數(shù)學(xué)原理：設(shè)有兩個(gè)數(shù)a和b，假設(shè)a比較大。令余數(shù)r = a% b。當(dāng)r == 0時(shí)，即a可以整除num2，顯然num2就是這兩個(gè)數(shù)的最大公約數(shù)。當(dāng)r ！= 0時(shí)，令a =b（除數(shù)變被除數(shù)），b = r（余數(shù)變除數(shù)），再做 r = a %b。遞歸，直到r == 0。

源程序如下：

#include

int maxgcd （int m，int n）

{ if（m%n==0）

return n；

else

return maxgcd（n，m%n）；

}

main（）

{ int a，b，temp；

printf（"please input two integer number："）；

scanf（"%d%d"，&a;，&b;）；

temp=maxgcd（a，b）；

printf（"The maxgys is %d＼n"，temp）；/*最大公約數(shù)*/

printf（"The min common multiple is %d＼n"，a*b/temp）；/*最小公倍數(shù)*/

getchar（）；

}

（4）應(yīng)用四：組合問題

問題：找出從自然數(shù)1、2、……、n中任取r個(gè)數(shù)的所有組合。例如n=4，r=3的所有組合為。

分析：n=4，r=3的所有組合為

（1）4、3、2（2）4、3、1（3）4、2、1

（4）3、2、1

分析所列的10個(gè)組合，可以采用這樣的遞歸來考慮。設(shè)函數(shù)為void ab（int n，int r）為找出從自然數(shù)1、2、……、n中任取r個(gè)數(shù)的所有組合。當(dāng)組合的第一個(gè)數(shù)字選定時(shí)，其后的數(shù)字是從余下的n-1個(gè)數(shù)中取r-1數(shù)的組合。這就將求n個(gè)數(shù)中取r個(gè)數(shù)的組合問題轉(zhuǎn)化成求n-1個(gè)數(shù)中取r-1個(gè)數(shù)的組合問題。設(shè)函數(shù)引入工作數(shù)組a[ ]存放求出的組合的數(shù)字，約定函數(shù)將確定的r個(gè)數(shù)字組合的第一個(gè)數(shù)字放在a[r]中，當(dāng)一個(gè)組合求出后，才將a[ ]中的一個(gè)組合輸出。第一個(gè)數(shù)可以是n、n-1、……、r，函數(shù)將確定組合的第一個(gè)數(shù)字放入數(shù)組后，有兩種可能的選擇，因還未去頂組合的其余元素，繼續(xù)遞歸去確定；或因已確定了組合的全部元素，輸出這個(gè)組合。細(xì)節(jié)見以下程序中的函數(shù)ab。

源程序如下：

# include “stdio.h”

# define max 10

int x[max]；

void zuhe（int n，int r）

{ int i，j；

for （i=n；i>=r；i--）

{ x[r]=i；

if （r>1）

zuhe（i-1，r-1）；

else

{ for （j=x[0]；j>0；j--）

printf（“%3d”x[j]）；

printf（“＼n”）；

}

}

}

main（）

{ x[0]=3；

zuhe（4，3）；

}

（5）應(yīng)用五： 爬樓梯問題

一個(gè)人上臺階可以一次上1個(gè)，2個(gè)，或者3個(gè)，問這個(gè)人上n層的臺階，總共有幾種走法？

分析：第一次走有三種情況：走一步或者兩步或者三步。若走一步，則是剩下 n-1個(gè)臺階；若走二步，則是剩下 n-2個(gè)臺階；若走三步，則是剩下 n-3個(gè)臺階；我們記f（n）表示下n層樓梯的方法總數(shù)，因?yàn)橛腥N方法可以走，那么有f（n）=f（n-1）+f（n-2）+f（n-3）這個(gè)遞歸公式，其中f（n-1）代表第一次走一步后的數(shù)目，f（n-2）代表第一次走兩步后的數(shù)目，f（n-3）代表第一次走三步后的數(shù)目。利用遞歸思想，直至最后剩下的步數(shù)是1，2，3，作為遞歸終止條件。根據(jù)分析f（1）=1；f（2）=2，包括1+1和2；f（3）=4；包括1+1+1，1+2，2+1，3。

源程序如下：

#include

int fun（int n）

{

if（n == 1） return 1

else if（n==2） return 2；

else if（n==3） return 4；

else

return fun（n-1） + fun（n-2）+fun（n-3）；

}

void main（）

{int n；

scanf（"%d"， &n;）；

printf（"%d"， fun（n））；

getchar（）；

}

4 遞歸總結(jié)：遞歸算法的三個(gè)要求

一是每次在調(diào)用時(shí)，直接或間接調(diào)用函數(shù)本身，每次調(diào)用后在規(guī)模上有所減小，且分解問題的方法相同，這樣在分析程序時(shí)本身就構(gòu)成了一個(gè)循環(huán)；

二是相鄰兩次調(diào)用一定存在著緊密的聯(lián)系，前一次（規(guī)模為n-1的問題）要為后一次（規(guī)模為n的問題）做準(zhǔn)備，一般來說，前一次的輸出應(yīng)作為后一次的輸入，前后二次調(diào)用緊密相關(guān)；

三是所有遞歸問題都可以用其他的算法來解決，但使用其他方法比較難解決，而使用函數(shù)的遞歸調(diào)用能很好地解決，分析思路清晰，且編寫的程序簡潔明了，又有較好的可讀性；但由于在遞歸調(diào)用中，每次調(diào)用系統(tǒng)要為變量開辟內(nèi)存空間、且每次調(diào)用要記住每一層調(diào)用后的返回點(diǎn)、這樣勢必增加許多額外的內(nèi)存開銷，因此函數(shù)的遞歸調(diào)用通常會降低程序的運(yùn)行效率。

【通聯(lián)編輯：代影】