遞迴是什麼意思

在電腦科學中，遞迴（Recursion）是一種解決問題的方法，它涉及將問題縮小為一個更小的子問題，並且重複這個過程，直到問題可以簡單地解決。遞迴通常涉及一個遞迴函數，該函數在其定義中調用自身。

遞迴有幾個關鍵部分：

1. 基線情況（Base case）：這是遞迴調用的終點，當滿足某個條件時，遞迴將不再繼續，並且直接返回解決方案。

2. 縮小問題：遞迴函數應該有一種方法來縮小問題，以便逐步接近基線情況。

3. 遞迴調用：函數應該在適當的時候調用自身，以解決更大的問題。

遞迴的一個例子是計算一個數字的 factorial（階乘）。 Factorial 運算的定義是，一個正整數的階乘是其所有更小的正整數的階乘的乘積，直到 1 的階乘，即 0 的階乘被定義為 1。因此，5! = 5 × 4 × 3 × 2 × 1。

一個遞迴的 factorial 函數可能如下定義：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

這個函數的基線情況是當 n 為 0 時，返回 1。對於所有其他正整數 n，它通過乘以 n 到 n-1 的階乘來縮小問題，並再次調用 factorial 函數。

遞迴的一個重要特點是，它可以用迴圈（如 for 或 while 迴圈）來實現，並且在許多情況下，迴圈可能更有效，因為它們避免了堆疊開銷，這是在許多程式設計語言中實現遞迴時的額外處理成本。然而，遞迴有時更直觀，更容易理解，並且在某些情況下可能是更自然的解決方案。