通俗講：資料結構遞歸思想
腦容量有限，拒絕花裡胡哨
一個遞歸求階乘的例子#如5的階乘 f(6)=6*5*4*3*2*1
def f(int n) {
if n <= 0 : return 1
return n * f(n - 1)
}
如果沒有特殊說明，下文都是拿此例子說事
通俗講：遞歸
- 遞歸就是 函數内調用自己
f(n - 1)
- 一個問題可以分解成具有 相同解決思路 的子問題才可以使用遞歸
- 遞歸函數 必須有結束出口 :
n <= 9
- 函數内調用時 參數一緻 ,如調用
f()
- 遞歸方式可以轉換成疊代（周遊）方式
-
return f(n-1)
return 1
記住以上黑體字，你就能解決大部分的遞歸問題了
遞歸遞歸，先遞後歸
遞歸的優點和缺點
優點
- 代碼簡潔
- 易于了解 ，如在樹周遊中，遞歸的實作明顯比循環簡單。
缺點
- 每次調用都需要在記憶體棧中 配置設定空間 以儲存參數，傳回值和臨時變量， 降低了效率
- 遞歸的分解的多個小問題存在重疊的部分，即 存在重複計算
- 棧空間是有限的，當調用的次數太多，可能會超出棧的容量，造成 調用棧溢出
綜合各方面，疊代的效率更佳，但有些問題用疊代處理更複雜
用疊代思想去思考遞歸
-
循環結束條件
-
循環體
-
進行下一次循環
解題心得
- 一定 不要試圖跟蹤大型遞歸的過程 ，否則會你讓頭腦炸裂，甚至懷疑人生
- 在調用遞歸的時候 利用整體思想，預設f(n)這個整體已經被求出來了 ,至于怎麼求的由計算機來回溯求出。如上面的求階乘的例子中
當n=6時 6 * f(5)
f(5)=5*4*3*2*1=120
- 解題時要清楚 遞歸函數功能、結束出口、要處理的子問題是什麼、函數調用位置和次數 如在求階乘中： 函數功能 就是求n的階乘并傳回， 結束出口 就是
n<=1
用目前數乘以 n-1的階乘
在有觸發結束遞歸的情況下， 遞歸調用=子問題處理+遞歸調用 ，也就是說一次遞歸調用從整體上看是實作函數功能，從局部上看就是處理一次子問題
上例題
例 1：給出一個整數num，反複将num各個位上的數字相加，直到結果為一位數- 函數功能：累加各位數直至結果為一位
- 結束出口: num<10
- 子問題:将num各位上的數字相加
- 遞歸調用位置：在求出num後調用一次
#遞歸法
def addDigits(self, num: int) -> int:
#1遞歸出口，直到結果為一位數即 num<10
if num < 10: return num
#2.處理子問題：反複将num各個位上的數字相加
temp = str(num)
s = 0
for a in temp:
s += int(a)
#3.傳回遞歸調用:沒達到需求，繼續遞歸
return self.addDigits(s)
：給定 N，計算 F(N)
- 函數功能：計算 F(N)
- 結束出口: N == 0 or N ==1
- 子問題:計算前倆F(n-1)和F(n-2)，這裡用整體思想，預設這兩個已知
- 遞歸調用位置：調用2次，即直接傳回
F(n-1)+F(n-2)
class Solution:
def fib(self, N: int) -> int:
#結束出口
if N == 1 : return 1
if N == 0 : return 0
#處理子問題（前兩者相加）+遞歸調用
return self.fib(N-1)+self.fib(N-2)
解決思路：
- 首先将最上面的n-1個盤子從A移到B柱子
- 然後将最下面的一個盤子從A移到C柱子
- 最後将n-1個盤子從B移到C柱子
注意:遞歸函數 需要處理的子問題是：将最底部的元素移到盤子C中
#主函數
def hanota(self, A, B, C):
'''
A: List[int] 初始資料清單
B: List[int] 輔助移動資料清單
C: List[int] 最終移動資料清單
return: None
'''
n = len(A)
self.move(n, A, B, C)
# 定義move函數移動漢諾塔（遞歸函數）
#子問題:将A盤子最底部元素借助盤子B移動到盤子C
def move(self,n, A, B, C):
#結束條件
if n == 1:
C.append(A.pop()) #移動最底的元素到C
return
#遞歸調用+處理子問題（将A的最後一個移到C）
self.move(n-1, A, C, B) # 将A上面n-1個通過C移到B
C.append(A.pop()) # 将A最後一個移到C
self.move(n-1,B, A, C) # 将B上面n-1個通過空的A移到C