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