背景知識

先了解一下內存結構，但這個不是必須的。

Definition

遞歸是一個循環結構，主要用來處理需要循環執行的任務，和For循環類似的代碼結構。
簡單說就是函(han)數(shu)自(zi)己能調用自(zi)己。

fun factorial(n:Int):Int{
  if(n <= 1) return n
  else return n*factorial(n-1)
}

用圖理解：

從堆棧的角度理解遞歸

遞歸的(de)底層就是利(li)用堆棧和指(zhi)令結(jie)構所(suo)實現的(de)功能。

缺點

從使用堆棧(zhan)的資源角(jiao)度來說，會(hui)比For以及其他循環(huan)結(jie)構更耗(hao)資源。

1. 內存開銷

• 堆棧：每次函數調用都會在棧上分配新的棧幀，包含參數、返回地址、局部變量等
• 循環：只在當前棧幀內重復執行，不需要額外的棧空間

2. 上下文切換成本

• 堆棧（遞歸）：涉及函數調用、返回地址保存、寄存器保存等操作
• 循環：簡單的跳轉指令，幾乎沒有上下文切換開銷

3. 緩存效率

• 堆棧：頻繁的函數調用可能導致緩存失效
• 循環：代碼局部性更好，緩存命中率更高

和For循環的區別

和For循環的區別有很多，但(dan)我主(zhu)要想討論(lun)他們對解決問題(ti)的思考方式上的差(cha)別。這個也是(shi)我想讓大家理解的第二(er)層含義。

如果說遞歸的第一層含義是：自己調用自己。
那么遞歸的第二層含義是：上一次的函數輸出，可以成為下一次函數的輸入。

案例——階梯問題：
我們以爬樓(lou)梯(ti)問題為例：有(you)n階臺階，每次可以爬1或2階，問有(you)多少種不同(tong)的方(fang)法爬到樓(lou)頂？

這(zhe)實際上就是求斐波那契(qi)數列。

遞歸終止條件：
當 n=1 時，只有1種方法：爬1階。
當 n=2 時，有(you)兩種方法：一次爬(pa)2階(jie)，或者兩次各爬(pa)1階(jie)。

對于n>2的情況，考慮第一步有兩種選擇：
第一步爬1階，那么剩下的n-1階臺階有 climb_stairs_recursive(n-1) 種方法。
第一步爬2階(jie)(jie)，那么剩下的n-2階(jie)(jie)臺階(jie)(jie)有(you) climb_stairs_recursive(n-2) 種方(fang)法。

因此，爬n階臺階的方法數等于這兩種情況的方法數之和，即：
climb_stairs_recursive(n) = climb_stairs_recursive(n-1) + climb_stairs_recursive(n-2)

舉個例子：n=3
第一步爬1階，剩下2階：有2種方法（爬2階：一次2階，或兩次1階）
第一步爬2階，剩下1階：有1種方法（爬1階）
所以總(zong)共2+1=3種(zhong)方法(fa)。

同理，n=4：
第一步爬1階，剩下3階：3種方法（上面n=3的情況）
第一步爬2階，剩下2階：2種方法（n=2的情況）
所以總共3+2=5種。

想要知道4階有多少種，那么需要先知道3階有多少種？
那么，想知道3階有多少種，那么就得知道2階有多少種？
一直追問(wen)到終止條件(jian)為止。

def climb_stairs_recursive(n):
    # 基礎情況
    if n == 1:
        return 1  # 只有1種方法：走1步
    if n == 2:
        return 2  # 2種方法：1→1 或 2

    # 遞歸關系：f(n) = f(n-1) + f(n-2)
    return climb_stairs_recursive(n-1) + climb_stairs_recursive(n-2)

為了(le)方(fang)便理解，加(jia)上(shang)了(le)打(da)印參數：

def climb_stairs_recursive(n, depth=0):
    indent = "  " * depth  # 根據深度縮進，顯示調用層次

    print(f"{indent}-> climb_stairs({n})")

    # 基礎情況
    if n == 1:
        print(f"{indent}<- 返回 1 (基礎情況: n=1)")
        return 1
    if n == 2:
        print(f"{indent}<- 返回 2 (基礎情況: n=2)")
        return 2

    # 遞歸調用
    print(f"{indent}  計算 climb_stairs({n - 1}) + climb_stairs({n - 2})")

    left = climb_stairs_recursive(n - 1, depth + 1)
    right = climb_stairs_recursive(n - 2, depth + 1)

    result = left + right
    print(f"{indent}<- 返回 {result} = {left} + {right}")

    return result


print("計算 climb_stairs(5):")
print(f"最終結果: {climb_stairs_recursive(5)}")

對比for循環的寫法：

# 需要在寫代碼的時候，自己維護狀態
def climb_stairs_iterative(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for i in range(3, n+1):
        a, b = b, a + b
    return b

在臺(tai)階(jie)問題（比如爬樓梯(ti)，每次可以走1步或(huo)2步，問n階(jie)臺(tai)階(jie)有多少種走法）中(zhong)，遞歸和循環都(dou)可以實現(xian)，但各有優劣。

遞歸方式的優點：

• 代碼直觀，易于理解：遞歸往往能夠直接反映問題的數學定義，比如斐波那契數列、爬樓梯問題的遞推關系。
• 易于設計和實現：對于復雜問題，遞歸可以簡化設計過程。

但是，在臺階問題中，遞歸的缺點也很明顯：

• 效率低：存在重復計算（遞歸層越大，重復計算則越多），導致指數級的時間復雜度。
• 棧溢出風險：當n較大時，遞歸深度過深，會導致棧溢出。
• 而循環（動態規劃）方式則通過迭代和保存中間結果，避免了重復計算，時間復雜度為O(n)，空間復雜度可以優化到O(1)。

總結

在(zai)快速原(yuan)型階段，可(ke)以使(shi)用遞歸是(shi)實現算(suan)法，好處是(shi)：

• 快速驗證算法思路
• 更容易修改和調整邏輯

方便快速實現。

而到了中后期的優化階(jie)段，可以(yi)考慮把循環結構(gou)改成動態規劃（for）循環，以(yi)節(jie)省內(nei)存資(zi)源。

還有，
遞(di)歸(gui)在直觀性和易于實現(xian)數學定義是其主要優點，但在內(nei)存性能上(shang)不(bu)如(ru)循環結構(gou)（動(dong)態(tai)規(gui)劃）。如(ru)果一個問(wen)題在初期(qi)就很容易用(yong)(yong)循環結構(gou)想清楚，則(ze)完全必要使用(yong)(yong)遞(di)歸(gui)（沒(mei)必要畫蛇添(tian)足）。

Reference

《秒(miao)懂算法》 作者：杰伊·溫格羅