在數學與計算機科學中，遞歸(recursion)是指一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法。它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大減少了程序的代碼量。遞歸的能力在于用有限的語句定義對象的無限集合。一個遞歸問題可分為遞推和回歸兩個階段。在遞推階段，把較復雜問題（規模為n）的求解推到比原問題簡單一些的問題（規模小于n）的求解；在回歸階段，當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解。
只有同時滿足下面三個條件的問題，才能用遞歸解決。
(1) 一個問題可以轉化為一個與原問題相似的、規模較小的子問題來求解。比如，在n的階乘的計算中，將n的階乘的問題轉化為n-1的階乘乘以n，此問題便可解決。
(2) 這個問題與分解之后的子問題，除數據規模不同，求解思路完全一樣。比如，n的階乘問題中，求解n的階乘的思路，和求解n-1的階乘的思路是一模一樣的。
(3) 存在遞歸終止條件。
把問題分解為子問題，再把子問題分解為子子問題，一層一層分解下去，不能存在無限循環，這就需要有終止條件。比如，n的階乘問題中，0或1的階乘為1，也就是f(1)=1，f(0)=1,這就是遞歸的終止條件。
遞歸是很多算法實現的基礎，是程序設計中的一種重要思想和機制，如分治、深度優先搜索、動態規劃等算法中均用到遞歸思想。
01、漢諾塔問題
漢諾（Hanoi）塔問題是一個經典的運用遞歸方法解決問題的例子。
問題描述:
漢諾塔是一個發源于印度的益智游戲，也叫河內塔。相傳它源于印度神話中的大梵天創造的三根金剛柱，一根柱子上疊著上下從小到大64個黃金圓盤。大梵天命令婆羅門將這些圓盤按從小到大的順序移動到另一根柱子上，其中大圓盤不能放在小圓盤上面。當這64個圓盤移動完的時候，世界就將毀滅。
那么，好多人會問64個圓盤移動到底會花多少時間？古代印度距離現在已經很遠，這64個圓盤還沒移動完么？我們通過計算看完成這個任務到底要多少時間？計算結果非常恐怖，移動圓盤的次數為2n-1，即18446744073709551615，假設移動一次圓盤用時一秒，一年為31536000秒。那么，18446744073709551615/31536000約等于584942417355年，即約為5850億年。目前太陽壽命約為50億年，太陽的完整壽命大約100億年。所以，整個人類文明都等不到移動完整圓盤的那一天。很多人對漢諾塔的解法產生了興趣。從一階漢諾塔到N階漢諾塔它們是否有規律性的算法？能否編程輸出每一次移動的方法呢？這就是本例要解決的問題。
輸入:
輸入一個正整數n，表示有n個圓盤在第一根柱子上。
輸出:
輸出操作序列，格式為move t from x to y。每個操作一行，表示把x柱子上的編號為t的盤片挪到柱子y上。柱子編號為a，b，c，要用最少的操作把所有盤子從a柱子上轉移到c柱子上。
輸入樣例:
3輸出樣例:
move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c解題思路:
實現這個算法，可以簡單分為以下三個步驟。
(1) 把第n-1個圓盤由a移到b。
(2) 把第n個圓盤由a移到c。
(3) 把第n-1個圓盤由b移到c。
從這里入手，加上上面數學問題解法的分析，不難發現，移動的步數必為奇數步。
(1) 第二步是把a柱子上剩下的一個盤子移到c柱子上。
(2) 第一步可以看成把a柱子上的n-1個圓盤借助c柱子移到b柱子上。
(3) 第三步可以看成把b上的n-1個圓盤借助a柱子移到c柱子上。
如3階漢諾塔的移動: A→C,A→B,C→B,A→C,B→A,B→C,A→C。
參考程序:
#include <fstream>
#include <iostream>
using namespace std;
/ *將x柱子上編號為 t的圓盤移動到 柱子上 * /
void Move(int t,char x,char y) [cout<<"move "<<t<<" from "<<x<<" to "<<y<<endl;
/*將 n個圓盤從 a 柱子借助 b 柱子移到 c 柱子 * /
void Hannoi(int n,char a,char b,char c)
{if(n==1)
move(1,a,c)
Move(1,a,c); /* 若只有一個圓盤，則直接將該圓盤由 a 柱子移到 c 柱子 * /
else
{
Hannoi(n-1,a,c,b); / * 把 a 柱子上的 n-1個圓盤借助 c 柱子移到 b 柱子上* /
Move(n,a,c); /*把 a 柱子上剩下的一個盤子移到 c 柱子上*/
Hannoi(n-1,b,a,c); /*把b 柱子上的 n-1個圓盤借助 a 柱子移到 c 柱子上* /}
})int main()
int n;
scanf("%d",&n);
Hannoi(n,'a','b','c') ;
return 0;
}02、木棒三角形
問題描述:
小A家里有很多長度不一的木棒，有一天他很無聊，擺弄這些木棒解悶。小A的數學學得很好，所以他想在這些木棒中挑出三根木棒組成一個直角三角形，當然，這可能有很多種選法，他還想挑出三根木棒組成一個面積最大的直角三角形。
輸入:
輸入有多組，每組輸入包括兩行，第一行輸入一個n(0≤n≤100)，表示小A有n根木棒，接著一行有n個整數（n≤1000），表示木棒的長度（長度從小到大給出）。
輸出:
輸出面積最大的直角三角形的面積，且保留3位小數，若不能組成，則輸出“My Good!”。
輸入數據:
4
1 2 3 4
5
2 3 4 5 6
6
3 4 5 6 8 10
2
1 1輸出數據:
My Good!
6.000
24.000
My Good!解題思路:
看到題目很容易想到如果求出從n根木棒中選出三根木棒的所有情況的解，那答案也就出來了。
現在的主要問題是怎么用程序枚舉所有情況。我們知道直角三角形的三條邊中斜邊是最長的，題目給出一個“長度從小到大給出”的條件，這樣我們可以依次枚舉三角形中長度最短、第二長和最長的邊，具體實現代碼如下。
參考程序:
#include< stdio.h>
#include<stdlib.h>
int main()
{
int i,j,k;
double ans;
int n;
int len[110];
while(scanf(rd",&n)!=EOF)
{for(i = 1;i <= n;i++)scanf("%d",&len[i]); //存儲木棒長度
ans = -1;
for(i = l;i <= n;i++){ //枚舉最短木棒
for(j = i+l;j <= n;j++){ //枚舉第二長的木棒
for(k = j+1;k <= n;k++){ //枚舉最長的木棒
if(len[i]*len[i] + len[j]*len[j] == len[k]* len[k]){ //如果是直角三角形
if(0.5*len[i]*len[j] > ans) //取最優解
ans = 0.5*len[i]*len[j];
}
}
}
}if(ans == -1)
printf("My Good! \n");
else
printf("%.3lf\n",ans);
}
)
)
