# 遞迴

## 1. 什麼是遞迴？
遞迴（Recursion）是一種程式設計技巧，函式會在其內部直接或間接呼叫自己。適用於問題可拆解為較小的相同問題，如數學計算、搜尋與排序。

## 2. 遞迴函式的結構

返回類型 函式名稱(參數) {
    // 終止條件
    if (條件滿足) {
        return 結果;
    }
    // 遞迴呼叫
    return 函式名稱(新參數);
}

**終止條件：** 確保遞迴不會無限執行，一定要加，不然妳可以試試，~~放心不會試試就逝世~~。
**遞迴步驟：** 逐步將問題縮小，直到符合終止條件。

## 3. 遞迴範例
### 費氏數列
#### 什麼是**費式數列**
由數學家**列昂納多·費波那契**（Leonardo Fibonacci）提出的數列，其特點是**每一項數字**都是**前兩項數字的和**。這個數列通常以 0 和 1 開始，之後的數字依照規則生成。

數列的數字如下所示： $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$

費式數列的定義：
$F(0) = 0$

$F(1) = 1$

$F(n) = F(n-1) + F(n-2) (n ≥ 2)$

##### 特點：
每個數字都是前兩個數字的和。
#### eg.

#include <iostream>
using namespace std;

int f(int n) {
    if (n <= 1) return n;  // 終止條件
    return f(n - 1) + f(n - 2);  // 遞迴步驟
}

int main() {
    int n = 5;
    cout << "F(n) = " << f(n) << endl;
    return 0;
}

** 輸出：**

F(5) = 5

### 階乘計算
這我應該不用多說吧!!

#include <iostream>
using namespace std;

int f(int n) {
    if (n == 0) return 1;  // 終止條件
    return n * f(n - 1);  // 遞迴步驟
}

int main() {
    int n = 5;
    cout << "F(n) = " << f(n) << endl;
    return 0;
}

** 輸出：**

F(5) = 120

## 4. 遞迴與迴圈的比較
| 比較項目 | 遞迴 | 迴圈 |
|----------|------|------|
| 可讀性 | 適合數學遞推問題 | 適合重複執行的邏輯 |
| 記憶體使用 | 可能較高（因為使用堆疊） | 佔用較少記憶體 |
| 效率 | 可能較低（函式呼叫有額外開銷） | 通常較快 |

## 5. 遞迴的應用
- **數學運算**：費氏數列、階乘、歐幾里得算法，甚至是河內塔問題都可以。
- **資料結構**：樹（Tree）、圖（Graph）的遍歷。
- **演算法**：合併排序（Merge Sort）、快速排序（Quick Sort）。

## 6. 結論
遞迴是一種強大的程式設計工具，適合解決可拆解為較小子問題的情境。但是，如果沒有妥善設定終止條件，可能導致無窮遞迴與記憶體溢位（Stack Overflow）。適時選擇迴圈或遞迴，能夠提升程式的效能與可讀性。

:::success
上面提到的 Stack Overflow 在記憶體分布有做介紹，他和資料結構的 stack 沒有什麼太大關係，所以不要誤會了。
:::