單元二 遞迴(Recursion)
===
遞迴是一個在程式設計中極具力量和靈活性的概念，它能夠以簡潔而優雅的方式解決許多複雜的問題。透過遞迴，我們可以將一個大問題分解成更小的子問題，從而更容易地理解和解決它們。
「遞迴是大事化小，要記得小事化無。」
此章節將簡單講述遞迴觀念以及一些例子。

---
觀念
---
### 遞迴是甚麼？
- 遞迴是一種解題的方法，主要是透過「重複呼叫自身程式碼」，將大問題切成小問題來找到解答。
### 他跟迭代有甚麼區別？
- **迭代**是利用迴圈(例如 for 或 while) 重複循環程式，來得到答案。
- **recursive(遞迴)** 與 **iterative(迭代)** 時常一起被提起，因為通常可以利用遞迴/迭代實作的程式，往往也能使用另一種方法實作。
### 比較
1. **概念複雜度：**
- **遞迴**通常更容易理解，因為它直接將問題分解為更小的子問題，並通過基本案例來終止遞迴。
- **迭代**需要額外的迴圈控制變量和條件，可能需要較多的思考和設計，尤其是對於複雜的問題。
2. **程式碼結構：**
- **遞迴**的程式碼通常較為簡潔明瞭，因為它將問題的解決方案直接表達為函式調用自身的方式。
- **迭代**的程式碼可能較為冗長，因為它需要額外的迴圈結構和變量。
:::spoiler #### **範例程式碼：**
(僅演示遞迴和迭代的差別，相同範例但寫法不同)

// 遞迴函式計算二元樹的最大深度
int maxDepthRecursive(TreeNode* node) {
    if (node == nullptr) return 0;
    int leftDepth = maxDepthRecursive(node->left);
    int rightDepth = maxDepthRecursive(node->right);
    return max(leftDepth, rightDepth) + 1;
}

// 迭代函式計算二元樹的最大深度
int maxDepthIterative(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }
        depth++;
    }
    return depth;
}

操作相同件事的程式碼，遞迴只用到了六行，而迭代卻需要十七行。
:::

3. **處理效率：**
* **迭代往往在處理效率方面表現得比較好**。因為遞迴每次呼叫自身時，都需要在堆疊上保存當前的狀態（包括參數、局部變數等），這個過程在深層遞迴時會**消耗大量的記憶體和時間**。然而迭代卻只使用固定的記憶體空間，因此開銷更小。

---
例題
---
學習遞迴是一件重要的事，不過遞迴的思考方式與一般的不同，它不是直接的給予答案，而是間接的說明答案與答案的關係。然而，傳統線性的思維模式不利於我們去撰寫遞迴，因此會有不少初學者對遞迴感到困難。
讓我們先以簡單的階乘為例：
### 例題一、階乘
數學定義：
$fac(n)=1\times2\times3\times\dots\times n，\forall n\gt 0$
讓我們以這個例子撰寫一段C++ 程式，輸出 $n$ 階乘：

int factorial(int n){
    if(n == 1 || n == 0) return 1;
    return n * factorial(n-1);
}

這段程式碼中的<font color="#e04">`factorial`</font>函式是一個遞迴函式。當輸入一個正整數 $n$ 時，該函式會遞迴地計算 $n$ 的階乘，直到達到基本案例，然後回溯並計算每個子問題的結果。最終，函式返回 $n$ 的階乘。

### 例題二、費波納契數列
數學定義：
\begin{equation*}
F_n =
\left\{
\begin{array}{}
0 &, n=0 \\
1 &, n=1 \\
F_{n-1}+F_{n-2}&, n>1 \\
\end{array}
\right.
\end{equation*}

int fibonacci(int n) {
    // 基本案例：當 n 為 0 或 1 時，返回 n
    if (n == 0 || n == 1) {
        return n;
    } else {
        // 遞迴步驟：費波納契數列的第 n 個數等於前兩個費波納契數的和
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

這段程式碼中的<font color="#e04">`fibonacci`</font>函式是一個遞迴函式。當輸入一個正整數$\mathit n$ 時，該函式會遞迴地計算費波納契數列的第$\mathit n$ 個數，直到達到基本案例，然後回溯並計算每個子問題的結果。最終，函式返回費波納契數列的第$\mathit n$ 個數。

---
實戰演練
---
### 簡單直觀題
[c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002)

McCarthy是一個有名的資訊專家。他定義了一個遞迴的函數叫做 f91 。它輸入一個正整數N並且依據以下的規則傳回一個正整數：
如果 $N <= 100$, 那麼 $f91(N) = f91( f91( N+11) )$，
如果 $N >= 101, 那麼 f91(N) = N-10$，
請你寫一個程式來計算 $f91$。

:::spoiler Ans：

#include <bits/stdc++.h>
using namespace std;

int f91(int x){
    if(x >= 101) return x-10;
    else return f91(f91(x+11));
}

int main(){
    int x;

    while(cin>>x){
        if(x == 0) break;
        else cout << "f91(" << x << ") = " << f91(x) << '\n';
    }
    return 0;
}

:::

### 有點難度題
[習題 Q-1-8. 子集合的和](https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a150)
#### 內容
輸入 $n$ 個正整數，請計算各種組合中，其和最接近 $P$ 但不超過 $P$ 的和是多少。
每個元素可以選取或不選取但不可重複選，輸入的數字可能重複。
$P≤1000000009，0<n<26。$
#### 輸入說明
第一行是 $n$ 與 $P$，
第二行 $n$ 個整數是 $A[i]$，
同行數字以空白間隔。
#### 輸出說明
最接近 $P$ 但不超過 $P$ 的和。
:::spoiler Ans:

#include <bits/stdc++.h>
using namespace std;

int arr[26]; // 儲存輸入數值的陣列
int n; // 數列的長度
int result; // 目標數值
int ans = 0; // 最接近目標數值且不超過它的數列子集合總和

// 遞迴函式，用於尋找最接近目標值的子集合總和
void fun(int index, int sum) {
    if(index == n) { // 如果已經考慮完所有元素
        return;
    }
    else if(sum >= result) { // 如果當前總和已經大於或等於目標值
        return;
    }
    fun(index + 1, sum); // 選擇不包含當前元素的情況
    sum += arr[index]; // 將當前元素加到總和中
    if(result - sum <= result - ans && result - sum > 0) { // 如果新的總和更接近目標值
        ans = sum; // 更新最佳解
    }
    fun(index + 1, sum); // 繼續尋找包含當前元素的情況
}

int main() {
    ios::sync_with_stdio(0); // 加速C++輸入輸出
    cin.tie(0); // 解除cin和cout的綁定，進一步加速輸入輸出
    cin >> n >> result;
    for(int i = 0; i < n; i++) {
        cin >> arr[i]; 
    }
    fun(0, 0); // 從第0個元素開始，嘗試找到最佳解
    cout << ans; 
    return 0;
}

程式碼使用遞迴函數<font color = "#a6f">`fun`</font>來尋找一個最適合的子集合，使得子集合的數字總和最接近`result`但不超過它。遞迴函數嘗試包含或不包含當前索引的元素，進而遍歷所有可能的子集合。
在遞迴的每一步，它都會檢查目前的總和是否比之前找到的任何總和更接近目標值。如果是，則將這個總和設定為新的最佳解。
:::

---
結語
---
在本篇講義中，我們介紹了遞迴這一編程技巧的核心概念、運用場景以及其在解決問題過程中的強大能力。透過具體例子的演練，我們理解了遞迴如何在程式碼中被實現。

遞迴作為一種思維模式，要求我們跳出傳統的線性解題思路，學會從問題的整體與部分之間建立聯繫，透過自我引用的方式逐步推進到解決方案

然而，遞迴的使用也需謹慎。不當的遞迴設計可能導致效率低下甚至執行失敗的問題，例如：堆疊溢位( stack overflow )。因此，掌握何時以及如何使用遞迴，是每一位優秀程式設計師所必須具備的能力。

總的來說，遞迴不僅豐富了我們解決問題的工具箱，也提升了我們的邏輯思維能力。希望透過本講義的學習，你能更加自信地運用遞迴，以創新的方式解決那些看似錯綜複雜的問題。