上網查了查，關於“遞歸”的文章可以說“汗牛充棟”——請原諒我在這裡犯酸，我的意思是，寫別人都寫臭的東西讓大家看，只是浪費大家的時間，所以我下面的東西應該是一些至少我看起來是新的東西，假如覺得有什麼不清楚的，請參閱相關的文章（太多了）。
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
即使這樣，這篇文章還是不能把我想說的寫完，看來我這人真的有廢話的習慣。
看過這樣一道題，問，“程序結構化設計的三種基礎結構，順序、選擇、循環是不是必須的？”當然，你知道這樣一個論斷，只要有這三種就足夠了；但是能不能更少呢？答案是“可以”，原因就是遞歸能取代循環的作用，例如下面的對一個數組裡面元素求和的函數：
float rsum (float a[], const int n)
{
if (n <= 0) return 0;
else return rsum(a, n – 1) + a[n – 1];
}
實際上就是：
sum = 0;
for (int i = 0; i < n; i++) sum += a[i];
但實際的情況是，任何的一種語言裡面都有循環結構，但不是任何的語言都支持遞歸；套用一句話，遞歸是萬能的，但沒有遞歸不是萬萬不能的。然而，我看到現在的某些人，不管什麼問題都要遞歸，明明循環是第一個想到的方法，偏偏費盡腦筋去尋找遞歸算法。對此，我真的不知道該說什麼。
遞歸是算法嗎
經常的看到“遞歸算法”、“非遞歸算法”，這種提法沒有語義上的問題，並且我自己也這樣用——遞歸的算法。但這也正說明了，遞歸不是算法，他是一種思想，正是因為某個算法的指導思想是遞歸的，所以才被稱為遞歸算法；而一個有遞歸算法的問題，當你不使用遞歸作為指導思想，這樣得到的算法就是非遞歸算法。——而對於循環能處理的問題，都有遞歸解法，在這個意義上說，循環算法都可以稱為非遞歸算法。
更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或
我在這咬文嚼字沒什麼別的意思，只是想讓大家知道，能寫出什麼樣的算法，要害是看你編寫算法時的指導思想。
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
假如一開始就想到了循環、迭代的方法，你再費心耗神去找什麼遞歸算法——即使找到了一種看似“簡潔”的算法，由於他的低效實際上還是廢物——你還在做這種無用功干什麼？典型的學究陋習。假如你僅僅想到了遞歸的方法，現在你想用棧來消解掉遞歸，你做的工作僅僅是把系統做的事自己做了，你又能把效率提高多少？盲目的迷信消解遞歸就一定能提高效率是無根據的——你做的工作的方法假如不得當的話，甚至還不如系統原來的做法。
從學排列組合那天開始，我所知道的階乘就是這個樣子n! = 1×2×……n。假如讓我來寫階乘的算法，我也只會想到從1乘到n。再如，斐波那契數列，假如有人用自然語言描述的話，一定是這樣的，開始兩項是0、1，以後的每項都是前面兩項的和。所以讓我寫也只會得到“保存前兩項，然後相加得到結果”的迭代解法。——現在只要是講到遞歸幾乎就有他們的登場，美其名曰：“定義是遞歸的，所以我們寫遞歸算法”。
我想問的是，定義的遞歸抽象是從哪裡來的？顯然階乘的定義是從一個循環過程抽象來的，斐波那契數列的定義是個迭代的抽象。於是，我們先從一個本不是遞歸的事實抽象出一個遞歸的定義，然後我們說，“因為問題的定義是遞歸的，因此我們很輕易寫出遞歸算法”，接著說，“我們也能將這個遞歸算法轉化為循環、迭代算法”，給人的感覺就像是1÷3＝0.33……，0.33……×3＝0.99……，然後我們花了好大的心智才明白1＝0.99……。
還是有那麼些人樂此不疲，是凡講到遞歸就要提到這兩個，結果，沒有一個學生看到階乘那樣定義沒有疑問的，沒有一個對於那個遞歸的階乘函數抱有欽佩之情的——瞎折騰什麼呢？所以，假如要講遞歸，就要一個令人信服的例子，而這個例子非漢諾塔莫屬。
更多內容請看C/C++技術專題 數據結構 數據結構教程專題，或
