想象一下，你現在要給一個朋友講一個“找東西”的故事。朋友問你：“這本書放在書架第幾層？”你記不清具體位置，只記得它在書架的中間，但中間有很多層。這時候你可能會說：“我先問問最上層的人，他知道下面的位置嗎？”不對，或許換個更簡單的例子：遞歸就像你在解決一個問題時，發現“這個問題需要先解決兩個更小的問題”，而這兩個小問題和原來的問題是同類型的。
一、什麼是遞歸？¶
遞歸的字面意思是“自己調用自己”，但更準確地說，它是一種將大問題分解成更小的同類問題，直到問題小到可以直接解決（稱爲“終止條件”），再通過小問題的結果反推大問題結果的方法。
舉個生活化的例子：
你想知道班級裏第10個同學的身高（假設已知班級所有人的身高），但你不記得具體是誰。於是你問：“第9個同學和第8個同學的身高分別是多少？”
第9個同學會問第8個和第7個，第8個同學會問第7個和第6個……直到你問到第1個同學（已知答案），然後逐層返回結果，最終算出第10個同學的身高。
二、斐波那契數列：遞歸的經典應用¶
斐波那契數列是一個非常經典的遞歸案例，它的定義很簡單：
- 第0個數（F(0)）是0
- 第1個數（F(1)）是1
- 從第2個數開始，每個數等於前兩個數之和：F(n) = F(n-1) + F(n-2)（n > 1）
比如：
F(0) = 0，F(1) = 1，F(2) = F(1)+F(0) = 1，F(3) = F(2)+F(1) = 2，F(4) = F(3)+F(2) = 3，F(5) = F(4)+F(3) = 5……
三、用遞歸計算斐波那契數列¶
我們用遞歸的思路來計算F(5)，看看它如何“分解”問題：
1. 終止條件：最小的問題¶
當n=0時，直接返回0；當n=1時，直接返回1。這兩個是已知的基礎情況，不需要再分解。
2. 遞歸條件：分解大問題¶
要計算F(n)，必須先計算F(n-1)和F(n-2)，然後把結果相加。
計算F(5)的步驟（從下往上）：¶
- 計算F(5) = F(4) + F(3)
- 計算F(4) = F(3) + F(2)
- 計算F(3) = F(2) + F(1)
- 計算F(2) = F(1) + F(0) = 1 + 0 = 1（終止條件）
- F(3) = F(2) + F(1) = 1 + 1 = 2（得到結果）
- F(4) = F(3) + F(2) = 2 + 1 = 3（得到結果）
- F(5) = F(4) + F(3) = 3 + 2 = 5（最終結果）
四、遞歸的核心：分解與終止¶
遞歸之所以“不繞”，是因爲它遵循兩個規則：
1. 終止條件：必須有明確的“不需要再分解”的情況（如F(0)和F(1)），否則會無限循環。
2. 問題規模遞減：每次遞歸調用時，問題的規模都在變小（如n從5變成4和3，再變成更小的數），確保最終能到達終止條件。
五、遞歸的代碼實現（Python舉例）¶
用幾行代碼就能寫出遞歸版本的斐波那契函數：
def fibonacci(n):
if n == 0: # 終止條件1：n=0時返回0
return 0
elif n == 1: # 終止條件2：n=1時返回1
return 1
else: # 遞歸條件：分解爲兩個小問題
return fibonacci(n-1) + fibonacci(n-2)
# 測試：計算F(5)
print(fibonacci(5)) # 輸出：5
六、遞歸的小總結¶
遞歸就像“拆解任務”：
- 先把大問題切成兩半“小問題”，直到小到能直接解決；
- 解決小問題後，再把結果合併成大問題的答案。
斐波那契數列的遞歸實現，用最簡單的邏輯（分解+終止）解決了“大數字斐波那契數”的計算問題。雖然遞歸看起來“繞”，但它讓代碼更簡潔，也體現了“以退爲進”的智慧——先解決小問題，再解決大問題。
思考：如果不用遞歸，直接用循環計算斐波那契數（迭代法）會怎麼樣？你可以試試對比兩種方法的差異，比如計算F(100)時遞歸會慢很多（爲什麼？），但遞歸的代碼更短。這就是遞歸的“優雅”與“代價”。