---

前言

??遞歸（Recursion）：指的是一種通過重復將原問題分解為同類的子問題而解決的方法。在絕大數編程語言中，可以通過在函數中再次調用函數自身的方式來實現遞歸。
??舉個簡單的例子來了解一下遞歸算法。比如階乘的計算方法在數學上的定義為：

def fact(n):if n == 0:return 1return n * fact(n - 1)

以 n=6為例，上述代碼中階乘函數的計算過程如下：

fact(6)
= 6 * fact(5)
= 6 * (5 * fact(4))
= 6 * (5 * (4 * fact(3)))
= 6 * (5 * (4 * (3 * fact(2))))
= 6 * (5 * (4 * (3 * (2 * fact(1)))))
= 6 * (5 * (4 * (3 * (2 * (1 * fact(0))))))
= 6 * (5 * (4 * (3 * (2 * (1 * 1)))))
= 6 * (5 * (4 * (3 * (2 * 1))))
= 6 * (5 * (4 * (3 * 2)))
= 6 * (5 * (4 * 6))
= 6 * (5 * 24)
= 6 * 120
= 720

??根據上面的描述，我們可以把階乘函數的遞歸計算過程分為兩個部分：

1. 先逐層向下調用自身，直到達到結束條件（即n==0。
2. 然后再向上逐層返回結果，直到返回原問題的解（即返回 fact(6)==720
   這兩個部分也可以叫做「遞推過程」和「回歸過程」，如下面兩幅圖所示：
   

??如上面所說，我們可以把「遞歸」分為兩個部分：「遞推過程」和「回歸過程」。
??? 遞推過程：指的是將原問題一層一層地分解為與原問題形式相同、規模更小的子問題，直到達到結束條件時停止，此時返回最底層子問題的解。
??? 回歸過程：指的是從最底層子問題的解開始，逆向逐一回歸，最終達到遞推開始時的原問題，返回原問題的解。
??「遞推過程」和「回歸過程」是遞歸算法的精髓。從這個角度來理解遞歸，遞歸的基本思想就是： 把規模大的問題不斷分解為子問題來解決。
??同時，因為解決原問題和不同規模的小問題往往使用的是相同的方法，所以就產生了函數調用函數自身的情況，這也是遞歸的定義所在。

遞歸和數學歸納法

??遞歸的數學模型其實就是「數學歸納法」。這里簡單復習一下數學歸納法的證明步驟：
??1.證明當n=b （b 為基本情況，通常為 0 或者 1）時，命題成立。
??2.證明n>b 時,假設n=k時命題成立，那么可以推導出n=k+1時命題成立；這一步不是直接證明的，而是先假設n=k時命題成立，利用這個條件，可以推論出n=k+1時命題成立。
??通過以上兩步證明，就可以說：當n>=b 時，命題都成立。
??我們可以從「數學歸納法」的角度來解釋遞歸：
??1.遞歸終止條件：數學歸納法第一步中的n=b，可以直接得出結果。
??2.遞推過程：數學歸納法第二步中的假設部分（假設n=k時命題成立），也就是假設我們當前已經知道了n=k時的計算結果。
??3.回歸過程：數學歸納法第二步中的推論部分,根據n=k推論出n=k+1）也就是根據下一層的結果，計算出上一層的結果。

遞歸三步走

??遞歸的基本思想就是： 把規模大的問題不斷分解為子問題來解決。 那么，在寫遞歸的時候，我們可以按照這個思想來書寫遞歸，具體步驟如下：
??1. 寫出遞推公式：找到將原問題分解為子問題的規律，并且根據規律寫出遞推公式。
??2. 明確終止條件：推敲出遞歸的終止條件，以及遞歸終止時的處理方法。
??3. 將遞推公式和終止條件翻譯成代碼：
????1. 定義遞歸函數（明確函數意義、傳入參數、返回結果等）。
????2. 書寫遞歸主體（提取重復的邏輯，縮小問題規模）。
????3. 明確遞歸終止條件（給出遞歸終止條件，以及遞歸終止時的處理方法）。

遞歸的注意點

避免棧溢出

??在程序執行中，遞歸是利用堆棧來實現的。每一次遞推都需要一個棧空間來保存調用記錄，每當進入一次函數調用，棧空間就會加一層棧幀。每一次回歸，棧空間就會減一層棧幀。由于系統中的棧空間大小不是無限的，所以，如果遞歸調用的次數過多，會導致棧空間溢出。
??為了避免棧溢出，我們可以在代碼中限制遞歸調用的最大深度來解決問題。當遞歸調用超過一定深度時（比如 100）之后，不再進行遞歸，而是直接返回報錯。
??當然這種做法并不能完全避免棧溢出，也無法完全解決問題，因為系統允許的最大遞歸深度跟當前剩余的占空間有關，事先無法計算。
??如果使用遞歸算法實在無法解決問題，我們可以考慮將遞歸算法變為非遞歸算法（即遞推算法）來解決棧溢出的問題。

避免重復運算

??在使用遞歸算法時，還可能會出現重復運算的問題。
??比如斐波那契數列的定義是

??從圖中可以看出：想要計算 f(5)，需要先計算 f(3) 和 f(4)，而在計算 f(4) 時還需要計算 f(3)，這樣f(3) 就進行了多次計算。同理 f(0)、f(1)、f(2) 都進行了多次計算，就導致了重復計算問題。
??為了避免重復計算，我們可以使用一個緩存（哈希表、集合或數組）來保存已經求解過的 f(k) 的結果，這也是動態規劃算法中的做法。當遞歸調用用到f(k) 時，先查看一下之前是否已經計算過結果，如果已經計算過，則直接從緩存中取值返回，而不用再遞推下去，這樣就避免了重復計算問題。

題目

斐波那契數

??遞推三步走策略，寫出對應的遞歸代碼。
??1寫出遞推公式：f(n)=f(n-1)+f(n-2)
??2 明確終止條件：f(0)=0,f(1)=1
??3 翻譯為遞歸代碼：
????1. 定義遞歸函數：fib(self, n) 表示輸入參數為問題的規模 n，返回結果為第 n 個斐波那契數。
????2. 書寫遞歸主體：return self.fib(n - 1) + self.fib(n - 2)。
????明確遞歸終止條件：
????1. if n == 0: return 0
????2. if n == 1: return 1

class Solution:def fib(self, n: int) -> int:if n == 0:return 0if n == 1:return 1return self.fib(n - 1) + self.fib(n - 2)

反轉鏈表

??描述：給定一個單鏈表的頭節點 head。
??要求：將該單鏈表進行反轉。可以迭代或遞歸地反轉鏈表。
示例
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
解釋：
翻轉前 1->2->3->4->5->NULL
反轉后 5->4->3->2->1->NULL

具體做法如下：

1. 首先定義遞歸函數含義為：將鏈表反轉，并返回反轉后的頭節點。
2. 然后從 head.next 的位置開始調用遞歸函數，即將 head.next 為頭節點的鏈表進行反轉，并返回該鏈表的頭節點。
3. 遞歸到鏈表的最后一個節點，將其作為最終的頭節點，即為 new_head。
4. 在每次遞歸函數返回的過程中，改變 head 和 head.next 的指向關系。也就是將 head.next 的next指針先指向當前節點 head，即 head.next.next = head 。
5. 然后讓當前節點 head 的 next 指針指向 None，從而實現從鏈表尾部開始的局部反轉。
6. 當遞歸從末尾開始順著遞歸棧的退出，從而將整個鏈表進行反轉。
7. 最后返回反轉后的鏈表頭節點 new_head。

1.class?Solution:
2.????def?reverseList(self,?head:?ListNode)?->?ListNode:
3.????????if?head?==?None?or?head.next?==?None:
4.????????????return?head
5.????????new_head?=?self.reverseList(head.next)
6.????????head.next.next?=?head
7.????????head.next?=?None
8.????????return?new_head