眾所周知,遞歸的實現是通過調用函數本身，函數調用的時候，每次調用時要做地址保存，參數傳遞等，這是通過一個遞歸工作棧實現的,同時影響效率的。遞歸是利用系統的堆棧保存函數當中的局部變量來解決問題的,而遞歸就是在棧處理棧上一堆的指針指向內存中的對象，這些對象一直不被釋放，直到遞歸執行到最后一次后，才釋放空間. ### 循環效率與遞歸效率 遞歸與循環是兩種不同的解決問題的典型思路。當然也并不是說循環效率就一定比遞歸高，遞歸和循環是兩碼事，遞歸帶有棧操作，循環則不一定，兩個概念不是一個層次，不同場景做不同的嘗試。  遞歸通常很直白地描述了一個求解過程，因此也是最容易被想到和實現的算法。循環其實和遞歸具有相同的特性（即：做重復任務），但有時，使用循環的算法并不會那么清晰地描述解決問題步驟。單從算法設計上看，遞歸和循環并無優劣之別。然而，在實際開發中，因為函數調用的開銷，遞歸常常會帶來性能問題，特別是在求解規模不確定的情況下。而循環因為沒有函數調用開銷，所以效率會比遞歸高。除少數編程語言對遞歸進行了優化外，大部分語言在實現遞歸算法時還是十分笨拙，由此帶來了如何將遞歸算法轉換為循環算法的問題。算法轉換應當建立在對求解過程充分理解的基礎上，有時甚至需要另辟蹊徑。 - 一般遞歸調用可以處理的算法，也通過循環去解決需要額外的低效處理。 - 現在的編譯器在優化后，對于多次調用的函數處理會有非常好的效率優化，效率未必低于循環。 - 遞歸和循環兩者完全可以互換。如果用到遞歸的地方可以很方便使用循環替換，而不影響程序的閱讀，那么替換成遞歸往往是好的。（例如：求階乘的遞歸實現與循環實現。） 要轉換成為非遞歸，兩步工作：第一步，可以自己建立一個堆棧保存這些局部變量，替換系統棧；第二步把對遞歸的調用轉變為循環處理就可以了。遞歸使用的棧布局.首先，看一下系統棧和用戶棧的用途。系統棧（也叫核心棧、內核棧）是內存中屬于操作系統空間的一塊區域，其主要用途為：保存中斷現場，對于嵌套中斷，被中斷程序的現場信息依次壓入系統棧，中斷返回時逆序彈出；以及保存操作系統子程序間相互調用的參數、返回值、返回點以及子程序(函數)的局部變量。用戶棧是用戶進程空間中的一塊區域，用于保存用戶進程的子程序間相互調用的參數、返回值、返回點以及子程序(函數)的局部變量。我們編寫的遞歸程序屬于用戶程序，因此使用的是用戶棧。 ### 循環與迭代 來自<<為之漫筆>>對這幾個概念的一段理解："loop、iterate、traversal and recursion".這幾個詞是計算機技術書中經常會出現的幾個詞匯,眾所周知，這幾個詞分別翻譯為：循環、迭代、遍歷和遞歸。乍一看，這幾個詞好像都與重復（repeat）有關，但有的又好像不完全是重復的意思。那么這幾個詞到底各是什么含義，有什么區別和聯系呢？即: - 循環（loop），指的是在滿足條件的情況下，重復執行同一段代碼。比如，while語句。 - 迭代（iterate），指的是按照某種順序逐個訪問列表中的每一項。比如，for語句。 - 遍歷（traversal），指的是按照一定的規則訪問樹形結構中的每個節點，而且每個節點都只訪問一次。 - 遞歸（recursion），指的是一個函數不斷調用自身的行為。比如，以編程方式輸出著名的斐波納契數列。 這幾個概念之間的區別其實就比較清楚了。至于它們之間的聯系，嚴格來講，它們似乎都屬于算法的范疇。換句話說，它們只不過是解決問題的不同手段和方式，而本質上則都是計算機編程中達成特定目標的途徑。 迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。利用迭代算法解決問題，需要三個方面的.**第一**確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量;**第二**建立迭代關系式。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式(或關系)。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。**第三**對迭代過程進行控制。在什么時候結束迭代過程?這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來;另一種是所需的迭代次數無法確定。對于前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制;對于后一種情況，需要進一步分析出用來結束迭代過程的條件。經典的迭代的算法問題如兔子產子問題和上樓梯的走法問題. 迭代與循環,先從字面上看：迭代：“迭”：輪流，輪番，替換，交替，更換。“代”：代替。所以迭代的意思是：變化的循環，這種變化就是輪番代替，輪流代替。而循環：不變的重復。或者迭代是循環的一種，循環體代碼分為固定循環體，和變化的循環體。 固定的循環如： ~~~ for(int i=0; i < 8; i++){ echo 'Welcome to AlgrithemMagic'; } ~~~ 實現迭代： ~~~ int sum = 0; for(int i = 1; i <= 1000; i++ ){ sum += i; } ~~~ 上面的迭代是常見的遞增式迭代。類似的還有遞減式迭代，遞乘式迭代。迭代的好處：迭代減少了冗余代碼，提高了代碼的利用率和動態性。 ### 循環、迭代與遞歸 遞歸算法與迭代算法的設計思路區別在于：函數或算法是否具備收斂性，當且僅當一個算法存在預期的收斂效果時，采用遞歸算法才是可行的，否則，就不能使用遞歸算法。當然，從理論上說，所有的遞歸函數都可以轉換為迭代函數，反之亦然，然而代價通常都是比較高的。但從算法結構來說，遞歸聲明的結構并不總能夠轉換為迭代結構，原因在于結構的引申本身屬于遞歸的概念，用迭代的方法在設計初期根本無法實現，這就像動多態的東西并不總是可以用靜多態的方法實現一樣。這也是為什么在結構設計時，通常采用遞歸的方式而不是采用迭代的方式的原因，一個極典型的例子類似于鏈表，使用遞歸定義及其簡單，但對于內存定義(數組方式)其定義及調用處理說明就變得很晦澀，尤其是在遇到環鏈、圖、網格等問題時，使用迭代方式從描述到實現上都變得很不現實。 遞歸其實是方便了程序員難為了機器。它只要得到數學公式就能很方便的寫出程序。優點就是易理解，容易編程。但遞歸是用棧機制實現的，每深入一層，都要占去一塊棧數據區域，對嵌套層數深的一些算法，遞歸會力不從心，空間上會以內存崩潰而告終，而且遞歸也帶來了大量的函數調用，這也有許多額外的時間開銷。所以在深度大時，它的時空性就不好了。循環其缺點就是不容易理解，編寫復雜問題時困難。優點是效率高。運行時間只因循環次數增加而增加，沒什么額外開銷。空間上沒有什么增加。 局部變量占用的內存是一次性的，也就是O(1)的空間復雜度，而對于遞歸,每次函數調用都要壓棧，那么空間復雜度是O(n)，和遞歸次數呈線性關系。 遞歸程序改用循環實現的話，一般都是要自己維護一個棧的，以便狀態的回溯。如果某個遞歸程序改用循環的時候根本就不需要維護棧，那其實這個遞歸程序這樣寫只是意義明顯一些，不一定要寫成遞歸形式。但很多遞歸程序就是為了利用函數自身在系統棧上的auto變量記錄狀態，以便回溯。原理上講，所有遞歸都是可以消除的，代價就是可能自己要維護一個棧。而且我個人認為，很多情況下用遞歸還是必要的，它往往能把復雜問題分解成更為簡單的步驟，而且很能反映問題的本質。 遞歸其實就是利用系統堆棧，實現函數自身調用，或者是相互調用的過程。在通往邊界的過程中，都會把單步地址保存下來，知道等出邊界，再按照先進后出的進行運算，這正如我們裝木桶一樣，每一次都只能把東西方在最上面，而取得時候，先放進取的反而最后取出。遞歸的數據傳送也類似。但是遞歸不能無限的進行下去，必須在一定條件下停止自身調用，因此它的邊界值應是明確的。就向我們裝木桶一樣，我們不能總是無限制的往里裝，必須在一定的時候把東西取出來。比較簡單的遞歸過程是階乘函數，你可以去看一下。但是遞歸的運算方法，往往決定了它的效率很低，因為數據要不斷的進棧出棧。但是遞歸作為比較基礎的算法，它的作用不能忽視。 關于[程序算法藝術與實踐](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多討論與交流，敬請關注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).