C++數據結構學習:遞歸(1)

2019-11-17 05:04:06

字體：大中小

來源：轉載

供稿：網友

　　上網查了查，關于“遞歸”的文章可以說“汗牛充棟”——請原諒我在這里犯酸，我的意思是，寫別人都寫臭的東西讓大家看，只是浪費大家的時間，所以我下面的東西應該是一些至少我看起來是新的東西，假如覺得有什么不清楚的，請參閱相關的文章（太多了）。

即使這樣，這篇文章還是不能把我想說的寫完，看來我這人真的有廢話的習慣。

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

　　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++技術專題數據結構數據結構教程專題，或　　我在這咬文嚼字沒什么別的意思，只是想讓大家知道，能寫出什么樣的算法，要害是看你編寫算法時的指導思想。

假如一開始就想到了循環、迭代的方法，你再費心耗神去找什么遞歸算法——即使找到了一種看似“簡潔”的算法，由于他的低效實際上還是廢物——你還在做這種無用功干什么？典型的學究陋習。假如你僅僅想到了遞歸的方法，現在你想用棧來消解掉遞歸，你做的工作僅僅是把系統做的事自己做了，你又能把效率提高多少？盲目的迷信消解遞歸就一定能提高效率是無根據的——你做的工作的方法假如不得當的話，甚至還不如系統原來的做法。
　　
　　從學排列組合那天開始，我所知道的階乘就是這個樣子n! = 1×2×……n。假如讓我來寫階乘的算法，我也只會想到從1乘到n。再如，斐波那契數列，假如有人用自然語言描述的話，一定是這樣的，開始兩項是0、1，以后的每項都是前面兩項的和。所以讓我寫也只會得到“保存前兩項，然后相加得到結果”的迭代解法。——現在只要是講到遞歸幾乎就有他們的登場，美其名曰：“定義是遞歸的，所以我們寫遞歸算法”。

　　我想問的是，定義的遞歸抽象是從哪里來的？顯然階乘的定義是從一個循環過程抽象來的，斐波那契數列的定義是個迭代的抽象。于是，我們先從一個本不是遞歸的事實抽象出一個遞歸的定義，然后我們說，“因為問題的定義是遞歸的，因此我們很輕易寫出遞歸算法”，接著說，“我們也能將這個遞歸算法轉化為循環、迭代算法”，給人的感覺就像是1÷3＝0.33……，0.33……×3＝0.99……，然后我們花了好大的心智才明白1＝0.99……。
　　
　　還是有那么些人樂此不疲，是凡講到遞歸就要提到這兩個，結果，沒有一個學生看到階乘那樣定義沒有疑問的，沒有一個對于那個遞歸的階乘函數抱有欽佩之情的——瞎折騰什么呢？所以，假如要講遞歸，就要一個令人信服的例子，而這個例子非漢諾塔莫屬。

更多內容請看C/C++技術專題數據結構數據結構教程專題，或

上一篇：C++數據結構學習:在鏈表中鏈入對象

下一篇：C++數據結構學習:遞歸(2-1)