本節主要說了遞歸的設計和算法實現，以及遞歸的基本例程斐波拉契數列、strlen的遞歸解法、漢諾塔和全排列遞歸算法。

一、遞歸的設計和實現

1.遞歸從實質上是一種數學的解決問題的思維，是一種分而治之的思想。

這個是常見的一種數學算法，其實它就是遞歸的本質。我們要求的是所有數的乘積，那么我們就先求出兩個數的乘積，然后再根據這兩個數的乘積去求第三個數的乘積，這樣每一次我們實際上都是進行的兩個數的相乘，也就是我們把一個很多個數的相乘轉換為了兩個數的相乘。

2.通過上面的例子可以發現，遞歸就是將大型復雜問題轉化為與原問題相同，但是規模變小的問題進行處理。

4.同時我們可以發現a1 這個時候n==1，是一個特殊的條件。這就是遞歸的邊界條件，最后的最后我們都會執行到遞歸的邊界條件，然后再從邊界條件返回。等到都返回結束后我們就真正實現了我們想要的結果。

5.如果遞歸沒有邊界條件，那么我們的遞歸將永遠無法跳出，也就是這個問題遞歸是無法解決的。

6.在解決遞歸問題的時候首先要建立遞歸模型，這是解決遞歸類問題的第一步。但是說來容易，其實這是一個痛苦的過程，說白了，算法不是一般人能搞的。

二、斐波拉切數列的遞歸實現

1.斐波拉切數列實際上就是一個遞歸的典型表現，它的具體要求如下：

通過上圖我們可以知道，斐波拉契數列的要求就是求相鄰兩個的數和然后賦給第三個數。這樣我們可以先求前兩個數的和，然后再求第二個與第三個數的和，一直求到最后，然后再返回。

2.假定我們要求的數列的元素個數為10

那么具體程序如下所示：

#include <stdio.h>int fibonacci(int n) {if( n > 1 ){return fibonacci(n-1) + fibonacci(n-2);}else if( n == 1 ){return 1;}else if( n == 0 ){return 0;} }int main() {int i = 0;for(i=1; i<=10; i++){printf("fibonacci(%d) = %d\n", i, fibonacci(i));}return 0; }

通過上面的程序可以看出：我們首先通過主函數調用fibonacci函數，然后通過for循環依次向里面傳遞值，第一次傳遞的值為1，返回的值為1，所以打印1.第二次傳遞的值為2，符合if(n>1)的條件，執行語句

fibonacci(n-1) + fibonacci(n-2);

這個時候產生第一輪遞歸，也就是先執行函數fibonacci(1)執行以后的返回結果是1，再執行fibonacci(0)，執行以后的返回結果是0，所以這一輪的返回結果是是1.

繼續調用fibonacci函數,傳遞的參數是3，然后依次向后執行，每一次的遞歸深度都在加深。

三、strlen函數使用遞歸方式實現

1.我們都知道strlen函數的使用方法，它是通過傳遞進來的字符串來判斷字符串的大小，但遇見"\0"的時候返回字符的個數，"\0"不包括在內。
2.假定我們要求一個"12345"的字符串的長度，具體例程如下：

#include <stdio.h>int strlen(const char* s) {if( s == NULL ){return -1;}else if( *s == '\0' ){return 0;}else{return strlen(s+1) + 1;} }int main() {printf("strlen(\"12345\") = %d\n", strlen("12345"));printf("strlen(NULL) = %d\n", strlen(NULL));printf("strlen(\"\") = %d\n", strlen(""));return 0; }

程序分析：我們在主函數中調用strlen函數，在我們第一次進入strlen函數的時候，程序執行判定，都不滿足前兩個判定，程序繼續向下執行，再次調用strlen函數，然后再進行判定，仍然不滿足判定條件，一直執行到s指針指向'\0'，這個時候各個調用函數開始返回，最外層的返回0，0+1，第二層返回1,1+1，第三層返回1,1+1 。直至所有函數全部返回。程序打印結果如下所示：

整個程序我們是把一個字符串的長度求解過程轉變成了對每一個字符長度的求解，然后再進行相加，邊界條件就是'\0'。

四、漢諾塔遞歸算法的實現

1.漢諾塔的要求我就不詳細說了，漢諾塔的問題我想了足足一天，其實最后也是單步調試加上草稿紙才把它搞定，這里拿三個盤子作為分析。

2.漢諾塔的遞歸思想：第一，把a上的n-1個盤通過c移動到b。第二，把a上的最下面的盤移到c。第三，因為n-1個盤全在b上了，所以把b當做a重復以上步驟就好了。
?

?3.漢諾塔的具體代碼實現：

#include <stdio.h>void hanoi(int n, char a, char b, char c) {if( n > 0 ){if( n == 1 ){printf("%c -> %c\n", a, c);}else{hanoi(n-1, a, c, b);printf("%c -> %c\n", a, c);hanoi(n-1, b, a, c);}} }int main() {hanoi(3, 'a', 'b', 'c');getchar(); return 0; }

程序打印結果如下：

五、漢諾塔遞歸調用分析

因為為了調試方便觀看值，所以我把a,b,c字符重新定義成了整型變量，具體程序如下：

#include <stdio.h>void hanoi(int n, int a, int b, int c) {if( n > 0 ) {if( n == 1 ){printf("%d -> %d\n", a, c);}else{hanoi(n-1, a, c, b);printf("%d -> %d\n", a, c);hanoi(n-1, b, a, c);}} }int main() {hanoi(3, 5, 6, 7);return 0; }

1.從主函數中調用hannoi函數，傳遞的參數是：n=3,a(1)=5,b(1)=6,c(1)=7
2.第1次進入hannoi函數，執行if(n==1)判定，不符合條件，調用hanoi(n-1,a,c,b)函數
3.向hannoi傳遞的參數是：n=2,a(2)=a(1),b(2)=c(1),c(2)=b(1)
4.第2次進入hannoi函數，執行if(n==1),不符合條件，調用hanoi(n-1,a,c,b)函數
5.向hannoi傳遞的參數：n=1,a(3)=a(2),b(3)=c(2),c(3)=b(2)
6.第3次進入hannoi函數，執行if(n==1)判定，符合條件，執行打印函數printf("%d->%d\n",a,c)這個時候打印函數里面的a,c是第3次調用hannoi函數傳遞進來的參數，也就是a3),c(3),追到原始值也就是a(1),c(1)。打印結果是：5->7
7.n=3的hannoi函數調用結束，子函數第1次執行結束。返回到n=2的hannoi函數調用位置，程序繼續向下執行
8.調用打印函數：printf("%d->%d\n",a,c)，這個時候打印函數的參數是n=2的時候hannoi函數的參數，也就是
a(2),c(2),追到原始值a(1),b(1)。打印結果是：5->6
9.執行完打印函數以后程序繼續向下執行，調用hanoi(n-1,b,a,c)函數
10.這次調用hanoi(n-1,b,a,c)是從n=2的hannoi函數開始的，所以向hannoi函數傳遞的參數是：n=1,a(4)=b(2),b(4)=a(2),c(4)=c(2)
11.第4次進入hannoi函數，指定if(n==1)判定，符合條件，執行打印函數printf("%d->%d\n",a,c)這個時候打印函數里的a,c是a(4),c(4),追到原始值c(1),b(1)，打印結果是：7->6.
12.調用hanoi(n-1,b,a,c)函數結束，程序返回到調用hanoi(n-1,b,a,c)函數的位置，接下來程序沒有語句，子函數再次結束，程序返回到n=3調用hannoi函數的位置，執行印函printf("%d->%d\n",a,c)，這個時候打印函數里的參數a,c是n=3的時候的參數，也就是a(1),c(1),追到原始值。打印結果是：5->7。
13.程序繼續向下執行，調用hanoi(n-1,b,a,c)函數
14.這個時候第一輪遞歸已經結束，向hannoi傳遞的參數是：n=2,a(5)=b(1),b(5)=a(1),c(5)=c(1)
15.第5次進入hannoi函數，執行if(n==1)判定，不符合條件，調用hannoi(n-1,a,c,b)函數
16.向hannoi傳遞的參數是：n=1,a(6)=a(5),b(6)=c(5),c(6)=b(5)
17.第6次進入hannoi函數，執行if(n==1)判定，符合條件，執行打印函數printf("%d->%d\n",a,c)這個打印函數里面的參數a,c是第6次調用hannoi函數的參數，也就是a(6),c(6),即b(1),a(1),追到原始值為6,5，打印結果是6->5
18.這個時候第6次進入hannoi函數執行完畢，程序返回到第六次調用hannoi函數的位置，繼續向下執行。
19.調用打印函數printf("%d->%d\n",a,c)，這個時候打印函數的參數a,c是n=2的時候第5次調用hannoi函數傳遞的參數，也就是a(5),c(5),追到原始值是b(1),c(1),即6,7.打印結果是6->7
20.程序繼續向下執行，調用hanoi(n-1,b,a,c)函數，這個時候程序是從n=2的hannoi函數位置繼續向下執行的，參數是：n=1,a(7)=b(5),b(7)=a(5),c(7)=c(5)
21.第七次進入hannoi函數，進行if(n==1)判定，符合條件，執行打印函數printf("%d->%d\n",a,c)，這個時候打印函數的參數是第七次調用hannoi函數的參數，也就是a(7),c(7)即b(5),c(5)，追到原始值5,7打印結果是：5->7
22.程序最后再一次返回兩次調用hanoi(n-1,b,a,c)函數的位置，但是每一次返回都沒有其他動作，直至程序結束。

程序分析的結果十分復雜和繁瑣，而且這僅僅是三層盤子。同時由于自己的畫圖水平不好，所以也沒有畫流程圖，同時網上好多大牛說是可以用樹的想法去想漢諾塔問題，但是我沒學習到樹，所以只能用上面那種最笨額方法了。

六、全排列的遞歸調用

1.問題的提出：假定有三個元素a,b,c，那么這三個元素的全排列有六種方式：abc,acb,bac,bca,cba,cab。那么兩個元素的全排列的是ab,ba，一個元素的全排列就是元素本身，所以一個元素的全排列就是遞歸的邊界條件。

2.我們這里以三個元素的全排列，程序例程如下：

#include <stdio.h>void permutation(char s[], int b, int e) {if( (0 <= b) && (b <= e) ){if( b == e ){printf("%s\n", s);}else{int i = 0;for(i=b; i<=e; i++){char c = s[b];s[b] = s[i];s[i] = c;permutation(s, b+1, e);c = s[b];s[b] = s[i];s[i] = c;}}} }int main() {char s[] = "abcd";permutation(s, 0, 3);return 0; }

?程序的遞歸算法框圖如下所示：

?

?由于我們傳進子函數的四個字符的字符數組，所以這里我們直接執行else部分的函數，首先執行for循環，for循環從i=b開始，這樣我們第一輪for循環先做的交換代碼如下：

char c = s[b]; s[b] = s[i]; s[i] = c;

其實這個時候我們沒有完成任何交換，然后繼續調用permutation(s, b+1, e)函數，再次進入for循環，這個時候for循環是從i=b+1開始的，這個時候執行交換部分的代碼還會完成另一個元素的交換。實質上這個交換部分的代碼完成的就是將每一個元素作為第一個位置的作用，然后再進行其他操作。
for循環里的第二部分主要代碼如下：

c = s[b]; s[b] = s[i]; s[i] = c;

這一部分代碼的主要作用是在每一個permutation(s, b+1, e)進行彈出操作的時候開始執行，這樣我們就可以對后面的數進行全排列了。我們也就完成圖示的全排列操作。具體的遞歸過程可以例程單步調試來進行理解。

總結

以上是生活随笔為你收集整理的C语言数据结构----递归的应用（斐波拉契数列、汉诺塔、strlen的递归算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。