遞歸算法也是C語言算法中一個比較簡單與常用的算法，本文我們就來談談遞歸算法，我們首先了解一下什麼是遞歸算法，關於遞歸算法的概念只有一句話：一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).。 我們再來看看遞歸算法的特點： (1) 遞歸就是在過程或函數裡調用自身。 (2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。 (3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。 (4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。 再看看遞歸的分類： 直接遞歸 程序設計中，過程或函數直接或者間接調用自己，就被稱為遞歸調用。子程序直接調用自己，這稱為直接遞歸；嵌套關系的子程序A和B，內層的B調用外層的A，這是間接低歸；平級關系的子程序A和B，其中A調用了B，B調用了A，這也是間接遞歸，不過，這種間接遞歸用到了“超前引用”的規則。 下面，博主找到了一些有關於遞歸算法的題目。我們看看第一個題目。 這是一道很經典的題目：階乘。相信大部分的人都知道什麼是階乘，但是你如果不知道的話，不妨參見一下百度百科：階乘。 好了，其實這題非常簡單，我們只需要一個函數即可解決問題。 復制代碼 1 int recursive(int i) 2 { 3 int sum = 0; 4 if (0 == i) 5 return (1); 6 else 7 sum = i * recursive(i-1); 8 return sum; 9 } 復制代碼 就是上面的遞歸函數，這題我就不浪費篇幅講解了，重點放在第二個例題：漢諾塔問題。 一個廟裡有三個柱子，第一個有64個盤子，從上往下盤子越來越大。要求廟裡的老和尚把這64個盤子全部移動到第三個柱子上。移動的時候始終只能小盤子壓著大盤子。而且每次只能移動一個。1、此時老和尚（後面我們叫他第一個和尚）覺得很難，所以他想：要是有一個人能把前63個盤子先移動到第二個柱子上，我再把最後一個盤子直接移動到第三個柱子，再讓那個人把剛才的前63個盤子從第二個柱子上移動到第三個柱子上，我的任務就完成了，簡單。所以他找了比他年輕的和尚（後面我們叫他第二個和尚），命令： ① 你把前63個盤子移動到第二柱子上 ② 然後我自己把第64個盤子移動到第三個柱子上後 ③ 你把前63個盤子移動到第三柱子上 2、第二個和尚接了任務，也覺得很難，所以他也和第一個和尚一樣想：要是有一個人能把前62個盤子先移動到第三個柱子上，我再把最後一個盤子直接移動到第二個柱子，再讓那個人把剛才的前62個盤子從第三個柱子上移動到第三個柱子上，我的任務就完成了，簡單。所以他也找了比他年輕的和尚（後面我們叫他第三和尚），命令： ① 你把前62個盤子移動到第三柱子上 ② 然後我自己把第63個盤子移動到第二個柱子上後 ③ 你把前62個盤子移動到第二柱子上 3、第三個和尚接了任務，又把移動前61個盤子的任務依葫蘆話瓢的交給了第四個和尚，等等遞推下去，直到把任務交給了第64個和尚為止（估計第64個和尚很郁悶，沒機會也命令下別人，因為到他這裡盤子已經只有一個了）。 4、到此任務下交完成，到各司其職完成的時候了。完成回推了： 第64個和尚移動第1個盤子，把它移開，然後第63個和尚移動他給自己分配的第2個盤子。 第64個和尚再把第1個盤子移動到第2個盤子上。到這裡第64個和尚的任務完成，第63個和尚完成了第62個和尚交給他的任務的第一步。 從上面可以看出，只有第64個和尚的任務完成了，第63個和尚的任務才能完成，只有第2個和尚----第64個和尚的任務完成後，第1個和尚的任務才能完成。這是一個典型的遞歸問題。 現在我們以有3個盤子來分析： 第1個和尚命令： ① 第2個和尚你先把第一柱子前2個盤子移動到第二柱子。（借助第三個柱子） ② 第1個和尚我自己把第一柱子最後的盤子移動到第三柱子。 ③ 第2個和尚你把前2個盤子從第二柱子移動到第三柱子。 很顯然，第二步很容易實現。 其中第一步，第2個和尚他有2個盤子，他就命令： ① 第3個和尚你把第一柱子第1個盤子移動到第三柱子。（借助第二柱子） ② 第2個和尚我自己把第一柱子第2個盤子移動到第二柱子上。 ③ 第3個和尚你把第1個盤子從第三柱子移動到第二柱子。 同樣，第二步很容易實現，但第3個和尚他只需要移動1個盤子，所以他也不用在下派任務了。（注意：這就是停止遞歸的條件，也叫邊界值） 第三步可以分解為，第2個和尚還是有2個盤子，命令： ① 第3個和尚你把第二柱子上的第1個盤子移動到第一柱子。 ② 第2個和尚我把第2個盤子從第二柱子移動到第三柱子。 ③ 第3個和尚你把第一柱子上的盤子移動到第三柱子。 分析組合起來就是：1→3 1→2 3→2 借助第三個柱子移動到第二個柱子 |1→3 | 2→1 2→3 1→3借助第一個柱子移動到第三個柱子|共需要七步。 如果是4個盤子，則第一個和尚的命令中第1步和第3步各有3個盤子，所以各需要7步，共14步，再加上第1個和尚的1步，所以4個盤子總共需要移動7+1+7=15步，同樣，5個盤子需要15+1+15=31步，6個盤子需要31+1+31=64步……由此可以知道，移動n個盤子需要（2的n次方）-1步。 從上面整體綜合分析可知把n個盤子從1座（相當第一柱子）移到3座（相當第三柱子）： （1）把1座上（n-1）個盤子借助3座移到2座。 （2）把1座上第n個盤子移動3座。 （3）把2座上（n-1）個盤子借助1座移動3座。 下面用hanoi（n,a,b,c）表示把1座n個盤子借助2座移動到3座。 很明顯: (1)步上是 hanoi(n-1,1,3,2) (3)步上是 hanoi(n-1,2,1,3) 用C語言表示出來，就是： 復制代碼 1 #include <stdio.h> 2 int method(int n,char a, char b) 3 { 4 printf("number..%d..form..%c..to..%c.."n",n,a,b); 5 return 0; 6 } 7 int hanoi(int n,char a,char b,char c) 8 { 9 if( n==1 ) move (1,a,c); 10 else 11 { 12 hanoi(n-1,a,c,b); 13 move(n,a,c); 14 hanoi(n-1,b,a,c); 15 }; 16 return 0; 17 } 18 int main() 19 { 20 int num; 21 scanf("%d",&num); 22 hanoi(num,'A','B','C'); 23 return 0; 24 } 復制代碼 這就是遞歸算法，其實，在C語言中，遞歸算法比枚舉法還要實用，但是這兩種算法都很簡單。
