遞歸是程序設計中常用到的一種簡單易懂的方法，在很多場合下，利用遞歸可以大量減少代碼量。
遞歸往往能體現設計者頭腦的聰慧，簡單的遞歸函數省去了大段大段的代碼，讓人嘆服不已。那么，遞歸的設計又有怎樣的固定思路呢？本文將介紹遞歸與數學歸納法之間的聯系，希望給讀者一些啟迪。
數學歸納法是數學中重要的一種證明方法。當證明一個數學定理時，采用數學歸納法的思路是，先證明對于簡單的可以代入的數，定理成立；再在假設定理對某一數N成立的前提下，證明N+1也是定理成立。其實，數學歸納法利用的是遞推的原理，形象地可以叫做多米諾原理。因為N+1的成立就可以向前向后遞推所有數都成立。
而遞歸利用的也是遞推的原理，在整個程序中，反復實現的將是同一個原理。在這一點上，遞歸與數學歸納法本質是相同的。所以往往可以利用數學歸納法來設計遞歸的實現。計算機是數學應用的一個分支在這里體現的淋漓盡致。
這里我們先來看一個例子，非常簡單，設計一程序，求自然數N的階乘N！：
現在已知N!=N*(N-1)*(N-2)*(N-3)*…*2*1
首先可知當N=1時 N!=1
第二步可設當R(N)=N!，R(N+1)=(N+1)!
第三步，求R(N+1)與R(N)之間的關系。R(N)=N!，
而R(N+1)=(N+1)!=(N+1)*(N)*(N-1)*…*2*1=(N+1)*N!=(N+1)*R(N)
即：R(N+1)=(N+1)*R(N) =〉 R(N)=N*R(N-1)
現在根據這個公式草略地構造一個函數：
factorial (int N)
{
return N * factorial (N - 1) /* 遞歸部分 */
}
接下來補充截止部分，這一部分在整個過程中只使用一次，沒有它，程序就將無限遞歸下去。可以說它是程序運行棧的棧頂，到了它，就開始一步步退棧了。
函數改為：
factorial (int N)
{
if (N == 1) return 1;
return N * factorial (N - 1) /* 遞歸部分 */
}
上面的步驟是可以顛倒的，而且首先設計截至部分還要好一些。
現在來總結設計遞歸程序的步驟：
一、用數學歸納法分析問題，根據數學歸納法的第一步得出截至部分。
二、根據數學歸納法的第三步來構造函數的遞歸部分。其實這個求解過程就是找出R(N)與R(N-1)的關系式。
現在利用總結出的方法做一個練習，比較經典的漢諾塔。
漢諾塔想必大家都知道：三個立柱（命名為from、temp、to，from為圓盤初始所在立柱、to是目標立柱），N個直徑不相等的圓盤，將圓盤從from上一個一個移動在to上，要求，每次只能移動一個圓盤，而且只能在三個立柱之間移動。不能出現大盤壓小盤的情況。
首先用數學歸納法分析：
當只有一個圓盤的時候，我們可以確定唯一動作：直接將圓盤從from移動到to上。
現在假設有N個圓盤在from上，而我們可以將這些圓盤最終按要求移動到to上（當然也可以移動到temp上）。
那么我們可以證明如果有N+1個時候，我們也可以將圓盤全部按要求移動到to上：因為我們可以先將上面的N個移動到temp上（第二步已假設），再把剩下的最后一個移動到to上，再把temp上的移動到to上。
按照我們總結過的遞歸函數設計步驟來設計程序：
首先，確定截至部分：當只有一個圓盤移動的時候，直接將它移動到to上。即：if (n == 1) move (n, from, to);
（這里的move函數意義是將n號圓盤，或者說初始狀態下從上面數第n個圓盤，從from移動到to）
第二步確定遞歸部分，其實就是N+1與N的關系部分，就是紅色字體部分。現在開始把文字轉化為程序：
設Hanoi (int n, int from, int temp, int to)函數就是我們要求的漢諾塔實現函數，意義是將按直徑遞增摞在一起的n個圓盤從from按要求移動到to上，temp為輔助圓盤。
可寫出代碼：
Hanoi (n-1, from, temp); /* 先將上面的N個移動到temp上 */
move (n, from, to); /* 剩下的最后一個移動到to上 */
Hanoi (n-1, temp, to); /* 再把temp上的移動到to上 */
第二步完成，最后合成函數：
void
Hanoi (int n, int from, int temp, int to)
{
if (n == 1)
move (n, from, to);
else
{
Hanoi (n-1, from, temp);
move (n, from, to);
Hanoi (n-1, temp, to);
}
}
使用數學歸納法設計遞歸程序最大的好處就是可以使設計者擺脫對遞推的顧慮。因為你設計的代碼必定隱含著遞推的步驟。直接根據你的分析文字轉化為代碼即可。
public void moveit(int n, ref Stack src, ref Stack des)
{
if ( src.Count!=0)
{
int varTemp;
varTemp = (int)src.Pop();
if(des.Count!=0)
{
if (varTemp < (int)des.Peek())
{
des.Push(varTemp);
}
else
src.Push(varTemp);
}
else
des.Push(varTemp);
}
}
public void hanoi(int n,ref Stack from, ref Stack tmp, ref Stack to)
{
if (n==1)
moveit(n,ref from, ref to);
else
{
hanoi(n-1, ref from, ref to, ref tmp);
moveit(n, ref from,ref to);
hanoi(n-1, ref tmp, ref from, ref to);
}
}