遞歸算法看起來比較簡單，當總覺得沒能領會到它的精髓，平常也沒可以使用它。今天看到這篇文章，說的比較透徹：

  1，遞歸與循環(huán)之間的關系

  看過這樣一道題，問，“程序結構化設計的三種基礎結構，順序、選擇、循環(huán)是不是必須的？”當然，你知道這樣一個論斷，只要有這三種就足夠了；但是能不能更少呢？答案是“可以”，原因就是遞歸能取代循環(huán)的作用，例如下面的對一個數(shù)組里面元素求和的函數(shù)：

float rsum (float a, const int n)
{
if (n <= 0) return 0;
else return rsum(a, n – 1) + a;
}

　　實際上就是：

sum = 0;
for (int i = 0; i < n; i++) sum += a;

　　但實際的情況是，任何的一種語言里面都有循環(huán)結構，但不是任何的語言都支持遞歸；套用一句話，遞歸是萬能的，但沒有遞歸不是萬萬不能的。然而，我看到現(xiàn)在的某些人，不管什么問題都要遞歸，明明循環(huán)是第一個想到的方法，偏偏費盡腦筋去尋找遞歸算法。對此，我真的不知道該說什么。

     ------我的理解是，循環(huán)和遞歸是2種結構，能實現(xiàn)類似的功能，至于哪種效率高，很簡潔易懂，要具體情況具體分析了。

2，什么時候用遞歸,是必要的？ 

    從學排列組合那天開始，我所知道的階乘就是這個樣子n! = 1×2×……n。如果讓我來寫階乘的算法，我也只會想到從1乘到n。再如，斐波那契數(shù)列，如果有人用自然語言描述的話，一定是這樣的，開始兩項是0、1，以后的每項都是前面兩項的和。所以讓我寫也只會得到“保存前兩項，然后相加得到結果”的迭代解法?！F(xiàn)在只要是講到遞歸幾乎就有他們的登場，美其名曰：“定義是遞歸的，所以我們寫遞歸算法”。我想問的是，定義的遞歸抽象是從哪里來的？顯然階乘的定義是從一個循環(huán)過程抽象來的，斐波那契數(shù)列的定義是個迭代的抽象。于是，我們先從一個本不是遞歸的事實抽象出一個遞歸的定義，然后我們說，“因為問題的定義是遞歸的，因此我們很容易寫出遞歸算法”，接著說，“我們也能將這個遞歸算法轉化為循環(huán)、迭代算法”，給人的感覺就像是1÷3＝0.33……，0.33……×3＝0.99……，然后我們花了好大的心智才明白1＝0.99……。

　　還是有那么些人樂此不疲，是凡講到遞歸就要提到這兩個，結果，沒有一個學生看到階乘那樣定義沒有疑問的，沒有一個對于那個遞歸的階乘函數(shù)抱有欽佩之情的——瞎折騰什么呢？

  ————我的理解是，如果一個問題在解決時，被描述/被抽象為 前幾項的什么什么時（迭代），自然而然就會想到使用遞歸算法。

3，有效使用遞歸

     我的理解：有些問題用遞歸的方法來解決，非常合適，一個典型的例子就是漢諾塔。通過下面的使用非遞歸算法來求解漢諾塔的例子，讓我理解到：遞歸在于在于準確的回歸，并且可以有較大的深度（棧）。而人腦的逆推深度是有限的，而計算機要比人腦深很多。這種思維在某種程度上提高了人解決問題的能力！

  “但我堅信，如果一個問題能用分析的辦法解決——遞歸實際上就是一個分析解法，能將問題分解成－1規(guī)模的同等問題和移動一個盤子，如果這樣分解下去一定會有解，最后分解到移動1號盤子，問題就解決了——那么我也應該能用綜合的辦法解決，就是從當前的狀態(tài)來確定怎樣移動，而不是逆推得到決定。這是對實際工作過程的一個模擬，試想如果讓我們去搬盤子，我們肯定不會用遞歸來思考現(xiàn)在應該怎么搬——只要8個盤子，我們腦子里的“工作?！笨峙戮鸵绯隽恕覀円⒓礇Q定怎么搬，而不是從多少步之后的情景來知道怎么搬。下面我們通過模擬人的正向思維來尋找這個解法。

　　假設如下搬7個盤子的初始狀態(tài)（選用7個是因為我曾經寫出了一個1～6結果正確的算法，而在7個的時候才發(fā)現(xiàn)一個條件的選擇錯誤，具體大家自己嘗試吧），我們唯一的選擇就是搬動1號盤子，但是我們的問題是向B搬還是向C搬？

　　顯然，我們必須將7號盤子搬到C，在這之前要把6號搬到B，5號就要搬到C，……以此類推，就會得出結論（規(guī)律1）：當前柱最上面的盤子的目標柱應該是，從當前柱上“需要搬動的盤子”最下面一個的目標柱，向上交替交換目標柱到它時的目標柱。就是說，如果當前柱是A，需要移動m個盤子，從上面向下數(shù)的第m個盤子的目標柱是C，那么最上面的盤子的目標柱就是這樣：if (m % 2) 目標和第m個盤子的目標相同（C）;else 目標和第m個盤子的目標不同（B）。接下來，我們需要考慮如果發(fā)生了阻塞，該怎么辦，如下所示：

　　3號盤子的目標柱是C，但是已經有了1號盤子，我們最直覺的反映就是——將礙事的盤子搬到另一根柱子上面去。于是，我們要做的是（規(guī)律2）：保存當前柱的信息（柱子號、應該搬動的最下面一塊盤子的號，和它的目標柱），以備當障礙清除后回到現(xiàn)在的柱子繼續(xù)搬，將當前柱轉換為礙事的盤子所在的柱子。假設這樣若干步后，我們將7號盤子從A搬到了C，此時，保存當前柱號的棧一定是空了，我們該怎么辦呢？

　　顯而易見的，轉換當前柱為B，把6號盤子搬到C。由此可得出（規(guī)律3）：假設當前的問題規(guī)模為n，搬動第n個盤子到C后，問題規(guī)模減1，當前柱轉換到另一個柱子，最下面的盤子的目標柱為C。

　　綜上，我們已經把這個問題解決了，可以看出，關鍵是如何確定當前柱需要移動多少盤子，這個問題請大家自己考慮，給出如下例程，因為沒有經過任何優(yōu)化，本人的編碼水平又比較低，所以這個函數(shù)很慢——比遞歸的還慢10倍。

#include 
#include

using namespace std;
class Needle
{
public:
Needle() { a.push_back(100); }//每一個柱子都有一個底座
void push(int n) { a.push_back(n); }
int top() { return a.back(); }
int pop() { int n = a.back(); a.pop_back(); return n; }
int movenum(int n) { int i = 1;while (a > n) i++; return a.size() - i; }
int size() { return a.size(); }
int operator (int n) { return a; }
private:
vector a;
};

void Hanoi(int n)
{
Needle needle, ns;//3個柱子，ns是轉換柱子時的保存棧，借用了Needle的棧結構
int source = 0, target, target_m = 2, disk, m = n; 
for (int i = n; i > 0; i--) needle.push(i);//在A柱上放n個盤子
while (n)//問題規(guī)模為n，開始搬動
{
if (!m) { source = ns.pop(); target_m = ns.pop();
m = needle.movenum(ns.pop()); }//障礙盤子搬走后，回到原來的當前柱
if (m % 2) target = target_m; else target = 3 - source - target_m;//規(guī)律1的實現(xiàn)
if (needle.top() < needle.top())//當前柱頂端盤子可以搬動時，移動盤子
{
disk = needle.top();m--;
cout << disk << ' move ' << (char)(source + 0x41) << ' to '<< (char)(target + 0x41) << endl;//顯示搬動過程

needle.push(needle.pop());//在目標柱上面放盤子
if (disk == n) { source = 1 - source; target_m = 2; m = --n; }規(guī)律3的實現(xiàn)
}

else//規(guī)律2的實現(xiàn)
{
ns.push(needle.size() - m]);
ns.push(target_m); ns.push(source);
m = needle.movenum(needle.top());
target_m = 3 - source - target; source = target;
}
}
}

　　這個算法實現(xiàn)比遞歸算法復雜了很多（遞歸算法在網上、書上隨便都可以找到），而且還慢很多，似乎是多余的，然而，這是有現(xiàn)實意義的。我不知道現(xiàn)在還在搬64個盤子的僧人是怎么搬的，不過我猜想一定不是先遞歸到1個盤子，然后再搬——等遞歸出來，估計胡子一打把了（能不能在人世還兩說）。我們一定是馬上決定下一步怎么搬，就如我上面寫的那樣，這才是人的正常思維，而用遞歸來思考，想出來怎么搬的時候，黃瓜菜都涼了。正像我們做事的方法，雖然我今生今世完不成這項事業(yè)，但我一定要為后人完成我能完成的，而不是在那空想后人應該怎么完成——如果達不到最終的結果，那也一定保證向正確的方向前進，而不是呆在原地空想。

　　由此看出，計算機編程實際上和正常的做事步驟的差距還是很大的——我們的做事步驟如果直接用計算機來實現(xiàn)的話，其實并不能最優(yōu)，原因就是，實際中的相關性在計算機中可能并不存在——比如人腦的逆推深度是有限的，而計算機要比人腦深很多，論記憶的準確性，計算機要比人腦強很多。這也導致了一個普通的程序員和一個資深的程序員寫的算法的速度常常有天壤之別。因為，后者知道計算機喜歡怎么思考。

4，遞歸的最大缺陷：占用內存多

內容參考：http://bbs./thread-186018-1-1.html