背景知識

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

Definition

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

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

用圖理解：

從堆棧的角度理解遞歸

遞歸的底層就是利用堆棧和指令結構所實現的功能。

缺點

從使用堆棧的資源角度來說，會比For以及其他循環結構更耗資源。

內存開銷

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

上下文切換成本

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

緩存效率

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

和For循環的區別

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

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

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

這實際上就是求斐波那契數列。

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

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

因此，爬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階）
所以總共2+1=3種方法。

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

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

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)

為了方便理解，加上了打印參數：

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

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

遞歸方式的優點：

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

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

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

總結

在快速原型階段，可以使用遞歸是實現算法，好處是：

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

方便快速實現。

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

還有，
遞歸在直觀性和易于實現數學定義是其主要優點，但在內存性能上不如循環結構（動態規劃）。如果一個問題在初期就很容易用循環結構想清楚，則完全必要使用遞歸（沒必要畫蛇添足）。

Reference

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

https://zh.javascript.info/recursion

posted on 2025-11-03 19:05 Mysticbinary 閱讀(130) 評論(0) 收藏舉報

刷新頁面返回頂部