C語言中遞歸函數的應用

史春水

摘要：該文對C語言遞歸函數的定義及調用進行了分析，就遞歸函數的應用以例題的形式進行了詳細的講解，便于初學者掌握遞歸函數分析思路與方法。

關鍵詞：C語言；遞歸函數；遞歸調用；遞歸應用

中圖分類號：TP3 文獻標識碼：A 文章編號：1009-3044（2018）28-0271-02

1 遞歸函數定義

在結構化程序設計中，一個函數在其定義中直接或間接地調用該函數本身的一種方法。在函數中直接調用函數本身，稱為直接遞歸調用，如下圖1所示。在函數中調用其他函數，其他函數又調用原函數，就構成了函數自身的間接調用，稱為間接遞歸，如下圖2所示：

2 遞歸函數的幾個注意事項

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

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

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

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

3 遞歸函數的幾個典型應用

（1）應用一：求和問題

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

分析：設sum（n）為前n項的和，則sum（n-1）為前n-1項的和，則有sum（n）=sum（n-1）+n；也就是說要求前n項的和，只要求前n-1項的和再加上n的值，求前n-1項的和只要求前n-2項的和再加上n-1的值，依次類推，直到n=1時，sum（n）=1，這就是遞歸函數出口，然后回歸求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）應用二：猴子摘桃子問題

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

分析：設x1為前一天桃子數，設x2為第二天桃子數，則

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； //定義所剩桃子數

if（n==10）

{return 1；

}

else

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

printf（"第%d天所剩桃子%d個＼n"， n， num）； //天數，所剩桃子個數

}

return num；

}

main（）

{ int num = get（1）；

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

getchar（）；

}

（3）應用三：求2個數的最大公約數問題

數學原理：設有兩個數a和b，假設a比較大。令余數r = a% b。當r == 0時，即a可以整除num2，顯然num2就是這兩個數的最大公約數。當r ！= 0時，令a =b（除數變被除數），b = r（余數變除數），再做 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）；/*最大公約數*/

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

getchar（）；

}

（4）應用四：組合問題

問題：找出從自然數1、2、……、n中任取r個數的所有組合。例如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個組合，可以采用這樣的遞歸來考慮。設函數為void ab（int n，int r）為找出從自然數1、2、……、n中任取r個數的所有組合。當組合的第一個數字選定時，其后的數字是從余下的n-1個數中取r-1數的組合。這就將求n個數中取r個數的組合問題轉化成求n-1個數中取r-1個數的組合問題。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的r個數字組合的第一個數字放在a[r]中，當一個組合求出后，才將a[ ]中的一個組合輸出。第一個數可以是n、n-1、……、r，函數將確定組合的第一個數字放入數組后，有兩種可能的選擇，因還未去頂組合的其余元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數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）應用五： 爬樓梯問題

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

分析：第一次走有三種情況：走一步或者兩步或者三步。若走一步，則是剩下 n-1個臺階；若走二步，則是剩下 n-2個臺階；若走三步，則是剩下 n-3個臺階；我們記f（n）表示下n層樓梯的方法總數，因為有三種方法可以走，那么有f（n）=f（n-1）+f（n-2）+f（n-3）這個遞歸公式，其中f（n-1）代表第一次走一步后的數目，f（n-2）代表第一次走兩步后的數目，f（n-3）代表第一次走三步后的數目。利用遞歸思想，直至最后剩下的步數是1，2，3，作為遞歸終止條件。根據分析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 遞歸總結：遞歸算法的三個要求

一是每次在調用時，直接或間接調用函數本身，每次調用后在規模上有所減小，且分解問題的方法相同，這樣在分析程序時本身就構成了一個循環；

二是相鄰兩次調用一定存在著緊密的聯系，前一次（規模為n-1的問題）要為后一次（規模為n的問題）做準備，一般來說，前一次的輸出應作為后一次的輸入，前后二次調用緊密相關；

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

【通聯編輯：代影】