循環、迭代與遞歸

循環、迭代與遞歸

1. 遞歸演算法與迭代演算法的設計思路區別在於：函數或演算法是否具備收斂性，當且僅當一個演算法存在預期的收斂效果時，採用遞歸演算法才是可行的，否則，就不能使用遞歸演算法。

當然，從理論上說，所有的遞歸函數都可以轉換為迭代函數，反之亦然，然而代價通常都是比較高的。但從演算法結構來說，遞歸聲明的結構並不總能夠轉換為迭代結構，原因在於結構的引申本身屬於遞歸的概念，用迭代的方法在設計初期根本無法實現，這就像動多態的東西並不總是可以用靜多態的方法實現一樣。這也是為什麼在結構設計時，通常採用遞歸的方式而不是採用迭代的方式的原因，一個極典型的例子類似於鏈表，使用遞歸定義及其簡單，但對於內存定義(數組方式)其定義及調用處理說明就變得很晦澀，尤其是在遇到環鏈、圖、網格等問題時，使用迭代方式從描述到實現上都變得很不現實。

2. 遞歸其實是方便了程序員難為了機器。它只要得到數學公式就能很方便的寫出程序。優點就是易理解，容易編程。但遞歸是用棧機制實現的，每深入一層，都要佔去一塊棧數據區域，對嵌套層數深的一些演算法，遞歸會力不從心，空間上會以內存崩潰而告終，而且遞歸也帶來了大量的函數調用，這也有許多額外的時間開銷。所以在深度大時，它的時空性就不好了。

循環其缺點就是不容易理解，編寫複雜問題時困難。優點是效率高。運行時間只因循環次數增加而增加，沒什麼額外開銷。空間上沒有什麼增加。

3. 局部變數佔用的內存是一次性的，也就是O(1)的空間複雜度，而對於遞歸（不考慮尾遞歸優化的情況），每次函數調用都要壓棧，那麼空間複雜度是O(n)，和遞歸次數呈線性關係。

4. 遞歸程序改用循環實現的話，一般都是要自己維護一個棧的，以便狀態的回溯。如果某個遞歸程序改用循環的時候根本就不需要維護棧，那其實這個遞歸程序這樣寫只是意義明顯一些，不一定要寫成遞歸形式。但很多遞歸程序就是為了利用函數自身在系統棧上的auto變數記錄狀態，以便回溯。

原理上講，所有遞歸都是可以消除的，代價就是可能自己要維護一個棧。而且我個人認為，很多情況下用遞歸還是必要的，它往往能把複雜問題分解成更為簡單的步驟，而且很能反映問題的本質。

遞歸其實就是利用系統堆棧，實現函數自身調用，或者是相互調用的過程。在通往邊界的過程中，都會把單步地址保存下來，知道等出邊界，再按照先進後出的進行運算，這正如我們裝木桶一樣，每一次都只能把東西方在最上面，而取得時候，先放進取的反而最後取出。遞歸的數據傳送也類似。但是遞歸不能無限的進行下去，必須在一定條件下停止自身調用，因此它的邊界值應是明確的。就向我們裝木桶一樣，我們不能總是無限制的往裡裝，必須在一定的時候把東西取出來。比較簡單的遞歸過程是階乘函數，你可以去看一下。但是遞歸的運算方法，往往決定了它的效率很低，因為數據要不斷的進棧出棧。

但是遞歸作為比較基礎的演算法，它的作用不能忽視。

純粹個人見解

推薦閱讀：