遞歸方法

一、什么是遞歸

　　遞歸是指函數直接或間接調用自身的一種編程方法。調用的過程就是“遞”,返回的過程就是歸?；旧? 所有的遞歸問題都可以用遞推公式來表示。

二、遞歸滿足的三個條件

1. 一個問題的解可以分解為幾個子問題的解。何為子問題? 子問題就是數據規模更小的問題。

2,這個問題與分解之后的子問題, 除了數據規模不同, 求解思路完全一樣
3. 存在遞歸終止條件
把問題分解為子問題, 把子問題再分解為子子問題, 一層一層分解下去, 不能存在無限循環, 這就
需要有終止條件。

三、如何編寫遞歸代碼

寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律, 并且基于此寫出遞推公式, 然后再推敲終止條件, 最后將遞推公式和終止條件翻譯成代碼。

對于遞歸代碼, 這種試圖想清楚整個遞和歸過程的做法, 實際上是進入了一個思維誤區。 很多時候, 我們理解起來比較吃力, 主要原因就是自己給自己制

造了這種理解障礙。 那正確的思維方式應該是怎樣的呢?

如果一個問題 A 可以分解為若干子問題 B、 C、 D, 你可以假設子問題 B、 C、 D 已經解決, 在此基礎上思考如何解決問題 A。 而且, 你只需要思考問題

A 與子問題 B、 C、 D 兩層之間的關系即可,不需要一層一層往下思考子問題與子子問題, 子子問題與子子子問題之間的關系。 屏蔽掉遞歸細節, 這樣子理

解起來就簡單多了。因此, 編寫遞歸代碼的關鍵是, 只要遇到遞歸, 我們就把它抽象成一個遞推公式, 不用想一層層的調用關系, 不要試圖用人腦去分解遞

歸的每個步驟。

四、遞歸的優點和缺點

1.優點:代碼表達能力強,寫起來簡單

2.缺點:空間復雜度高,存在堆棧溢出風險、存在過多的重復計算、過多的耗時函數調用等。

參考:極客時間《數據結構與算法之美》