一、什麼是遞歸？¶

遞歸，簡單來說就是“自己調用自己”。想象一下俄羅斯套娃：你有一個大套娃，裏面裝着一個更小的套娃，這個小套娃裏又裝着更小的，直到最小的套娃裏沒有其他套娃了。遞歸就像這樣——一個問題被分解成更小的子問題，而每個子問題本身又是同一個問題的縮小版，直到子問題小到可以直接解決（不需要再分解），然後“反彈”回來得到最終結果。

二、遞歸的核心：終止條件 + 遞歸關係¶

遞歸有兩個關鍵要素，缺一不可：
1. 終止條件：當問題小到不能再分解時，直接返回結果（避免無限循環）。
2. 遞歸關係：如何把大問題分解成更小的子問題，讓每個子問題都用同樣的規則解決。

三、用斐波那契數列學遞歸¶

斐波那契數列是遞歸的經典例子，它的定義很簡單：
- 第 0 個數是 0（F(0) = 0）
- 第 1 個數是 1（F(1) = 1）
- 從第 2 個數開始，每個數等於前兩個數之和（F(n) = F(n-1) + F(n-2)）

現在我們用遞歸思想來求第 n 個斐波那契數：

1. 定義遞歸函數¶

假設我們要寫一個函數 fib(n)，返回第 n 個斐波那契數：

def fib(n):
    # 終止條件：n是0或1時，直接返回結果
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 遞歸關係：大問題分解爲小問題（調用自身）
    return fib(n-1) + fib(n-2)

2. 用例子拆解遞歸過程¶

以 fib(5) 爲例，看看遞歸如何一步步計算：
- 求 fib(5) 需要先求 fib(4) 和 fib(3)；
- 求 fib(4) 需要先求 fib(3) 和 fib(2)；
- 求 fib(3) 需要先求 fib(2) 和 fib(1)；
- 求 fib(2) 需要先求 fib(1) 和 fib(0)；
- 當到 fib(1) 時，直接返回 1；到 fib(0) 時，直接返回 0。

逐層返回結果：
- fib(2) = fib(1) + fib(0) = 1 + 0 = 1
- fib(3) = fib(2) + fib(1) = 1 + 1 = 2
- fib(4) = fib(3) + fib(2) = 2 + 1 = 3
- fib(5) = fib(4) + fib(3) = 3 + 2 = 5

所以，第 5 個斐波那契數是 5。

四、遞歸的“套路”：層層嵌套，觸底反彈¶

遞歸的過程就像“剝洋蔥”：從最外層的問題開始，一層一層往裏“挖”，直到挖到最內層的簡單問題（終止條件），然後再一層一層返回結果。沒有終止條件的遞歸會導致無限循環，比如忘記寫 n==0 或 n==1 的情況，程序會一直調用下去直到崩潰。

五、遞歸的優缺點（簡單提）¶

• 優點：邏輯清晰，容易理解和實現（比如斐波那契用遞歸幾行代碼就能解決）。
• 缺點：可能重複計算（比如 fib(5) 中 fib(3) 被計算了兩次），效率較低。如果需要優化，可以用“記憶化遞歸”或“迭代”解決。

六、總結¶

遞歸的本質是“把大問題變小，小問題解決後再組合成大問題的結果”。用斐波那契數列做例子，我們看到了遞歸如何通過“終止條件+遞歸關係”實現自調用，最終得到答案。記住：遞歸的關鍵是別讓它“越走越遠”，要確保它能“回頭”！

下次遇到需要分解成同類子問題的場景時，不妨試試遞歸的思路，也許會豁然開朗~