一、遞歸概述

應用：DSF深度優先搜索、前中后序二叉樹遍歷等

三個條件：

一個問題的解可以分解為幾個子問題的解

該問題與分解之后的子問題，除了數據規模不同，求解思路完全一樣

存在遞歸終止條件

寫遞歸代碼的關鍵:

• 如何將大問題分解為小問題的規律 =》寫出遞歸公式
• 確定終止條件
• 將遞推公式 和 終止條件 轉化為codes

優點：表達力強、非常簡潔；
缺點：空間復雜度高、有堆棧溢出的風險、存在重復計算、過多的函數調用耗時等問題。

二、注意

1、警惕堆棧溢出

影響：堆棧溢出 ==》系統性崩潰

原因：系統棧或虛擬機棧空間一般都不大。若遞歸求解的數據規模很大，調用層次很深，一直壓入棧，就會有堆棧溢出的風險。

措施：

設置遞歸調用的最大深度，也就是遞歸調用超過一定深度之后，就不繼續再遞歸下去，而是直接返回報錯。==》不是很實用

通過在堆上模擬實現一個函數調用棧，手動模擬壓棧、出棧的過程，這樣就沒有系統棧大小的限制。

2、警惕重復計算

例如：斐波那契數。eg：1、1、2、3、5、8、

從圖中可得==》f(3) 就被計算了很多次，這就是重復計算問題。

措施：

可以通過一個數據結構（例如散列表）來保存已經求解過的 f(k) 。當遞歸調用到 f(k) 時，先確定是否已經求解過了，若是則直接取數，否則再進行計算。

3、時間和空間復雜度

• 時間：調用的數量較大時 ==》時間成本
• 空間：每遞歸一次就會在內存棧中保存一個現場數據。

4、遞歸代碼 =》非遞歸代碼

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的六、递归(Recursion)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。