遞迴

本集目標

讓函數呼叫自己來解決問題，這個技巧叫做「遞迴」。

正文

你有沒有想過：函數可以在自己裡面呼叫自己嗎？

答案是可以的，而且這個技巧叫做遞迴（recursion）。聽起來很玄，但其實概念很簡單。

經典範例：階乘

「5 的階乘」寫成 5!，意思是 5 × 4 × 3 × 2 × 1 = 120。

用遞迴的思路想：

• 5! = 5 × 4!
• 4! = 4 × 3!
• 3! = 3 × 2!
• 2! = 2 × 1!
• 1! = 1（到這裡停下來）

看到了嗎？每一步都是「自己乘以比自己小一號的階乘」，最後到 1 就停。

fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

fn main() {
    println!("5! = {}", factorial(5));
    println!("3! = {}", factorial(3));
    println!("1! = {}", factorial(1));
}

遞迴的兩個關鍵

每個遞迴函數都需要兩樣東西：

1. base case（基底情況）：什麼時候停下來

if n <= 1 {
    1 // 停！不再呼叫自己
}

2. recursive case（遞迴情況）：怎麼把問題縮小

n * factorial(n - 1) // 把問題縮小：n 變成 n - 1

如果忘記寫 base case，函數就會無限呼叫自己，最後程式就炸了。

追蹤執行過程

讓我們追蹤 factorial(5) 的執行過程：

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

就像俄羅斯套娃一樣，一層一層展開，到底之後再一層一層收回來。

另一個例子：倒數

fn countdown(n: u32) {
    if n <= 0 {
        println!("發射！🚀");
        return;
    }
    println!("{}...", n);
    countdown(n - 1);
}

fn main() {
    countdown(5);
}

遞迴 vs 迴圈

其實上面的例子都可以用迴圈寫。那什麼時候用遞迴？什麼時候用迴圈？

• 簡單的重複 → 迴圈比較直覺
• 問題本身就是遞迴結構 → 遞迴比較自然

現在先知道遞迴怎麼寫就好，之後遇到適合的場景自然會用到。

重點整理

• 遞迴就是函數呼叫自己
• 一定要有 base case（停止條件），不然會無限迴圈
• 每次呼叫都要讓問題變小，往 base case 靠近