recursion_examples.cpp

/*
 * ============================================================================
 *  遞迴 (Recursion) 完整範例 — 遞迴版 vs 非遞迴（迭代）版
 *  File: recursion_examples.cpp
 *
 *  每個範例都同時提供遞迴版和迭代版，並說明轉換的方法。
 *
 *  範例列表：
 *    1.  階乘 (Factorial)           — 直接迴圈
 *    2.  階乘（尾遞迴版）           — 累加器參數
 *    3.  Fibonacci（天真遞迴）      — O(2^N) vs 迭代 O(N)
 *    4.  Fibonacci（Memoization）   — 記憶化 O(N)
 *    5.  二元搜尋 (Binary Search)   — 尾遞迴 → while
 *    6.  GCD（歐幾里得）           — 尾遞迴 → while
 *    7.  河內塔 (Tower of Hanoi)    — 手動 Stack
 *    8.  二元樹 Inorder 遍歷       — 手動 Stack
 *    9.  反轉字串                   — 雙指標
 *   10.  Quick Sort                — Stack 存區間
 *
 *  Compile: g++ -std=c++11 -Wall -o recursion_examples recursion_examples.cpp
 *  Run:     ./recursion_examples
 * ============================================================================
 */

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

/* ============================================================================
 *  1. 階乘 (Factorial)
 *
 *  定義: n! = n × (n-1) × ... × 1,  0! = 1
 *
 *  轉換方法：【直接用 for 迴圈取代】
 *    - 遞迴從 n 遞減到 0 → 迴圈從 1 遞增到 n
 *    - base case 的值 (1) → 迴圈的初始值
 * ============================================================================ */

// 遞迴版 — 每次呼叫 n 減 1，到 n=0 時回傳 1
// 時間 O(N)，空間 O(N)（call stack）
long long factorialRec(int n) {
    // Base case: 0! = 1
    if (n <= 0) return 1;
    // Recursive case: n! = n × (n-1)!
    return (long long)n * factorialRec(n - 1);
}

// 迭代版 — 用 for 迴圈累乘
// 時間 O(N)，空間 O(1)
long long factorialIter(int n) {
    long long result = 1;
    // 從 1 乘到 n（方向和遞迴相反）
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

/* ============================================================================
 *  2. 階乘（尾遞迴版）
 *
 *  轉換方法：【累加器 (accumulator) 參數】
 *    - 把「回來後要做的乘法」提前到參數裡
 *    - 遞迴呼叫是函式的最後一步 → 尾遞迴
 *    - 編譯器可優化為不使用額外 Stack 空間
 * ============================================================================ */

// 尾遞迴版 — acc 累積結果，遞迴呼叫是最後一步
// 時間 O(N)，空間 O(1)（若編譯器做 TCO）
long long factorialTail(int n, long long acc = 1) {
    // Base case: 累積完畢
    if (n <= 0) return acc;
    // Tail call: 把 n * acc 往下傳，回來後不再做任何運算
    return factorialTail(n - 1, (long long)n * acc);
}

/* ============================================================================
 *  3. Fibonacci
 *
 *  定義: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
 *
 *  天真遞迴: O(2^N) — 大量重複計算，極慢！
 *  迭代:     O(N)   — 只保留前兩項
 *
 *  轉換方法：【Bottom-up 迴圈（動態規劃）】
 *    - 遞迴是 top-down (從 n 往 0)
 *    - 迭代是 bottom-up (從 0 往 n)
 * ============================================================================ */

// 遞迴版 — O(2^N)，n > 40 就非常慢
long long fibRec(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    // 兩個遞迴呼叫 → 指數級爆炸
    return fibRec(n - 1) + fibRec(n - 2);
}

// 迭代版 — O(N) 時間，O(1) 空間
long long fibIter(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; ++i) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

/* ============================================================================
 *  4. Fibonacci（Memoization 記憶化）
 *
 *  轉換方法：【加一個陣列/map 記錄已算過的結果】
 *    - 保持遞迴的寫法，但避免重複計算
 *    - 時間從 O(2^N) 降到 O(N)
 *    - 空間 O(N)（memo 陣列）
 * ============================================================================ */
static vector<long long> memo;

long long fibMemo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    // 如果已經算過，直接回傳
    if (memo[n] != -1) return memo[n];
    // 否則算一次，存起來
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

/* ============================================================================
 *  5. 二元搜尋 (Binary Search)
 *
 *  在已排序陣列中尋找 target。
 *
 *  轉換方法：【尾遞迴 → while 迴圈】
 *    - 遞迴呼叫是最後一步（尾遞迴）
 *    - 用 while 迴圈直接更新 low/high
 * ============================================================================ */

// 遞迴版
int bsRec(const vector<int>& a, int low, int high, int target) {
    // Base case: 沒找到
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == target) return mid;
    if (target < a[mid])
        return bsRec(a, low, mid - 1, target);   // 搜尋左半
    else
        return bsRec(a, mid + 1, high, target);   // 搜尋右半
}

// 迭代版 — 把遞迴的「更新參數」改為「更新變數」
int bsIter(const vector<int>& a, int target) {
    int low = 0, high = (int)a.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (target < a[mid])
            high = mid - 1;   // 對應 bsRec(a, low, mid-1, target)
        else
            low = mid + 1;    // 對應 bsRec(a, mid+1, high, target)
    }
    return -1;
}

/* ============================================================================
 *  6. GCD — 歐幾里得演算法
 *
 *  gcd(a, b) = gcd(b, a % b),  gcd(a, 0) = a
 *
 *  轉換方法：【尾遞迴 → while 迴圈】
 * ============================================================================ */

// 遞迴版（天然的尾遞迴）
long long gcdRec(long long a, long long b) {
    if (b == 0) return a;
    return gcdRec(b, a % b);
}

// 迭代版
long long gcdIter(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/* ============================================================================
 *  7. 河內塔 (Tower of Hanoi)
 *
 *  轉換方法：【手動模擬 Stack】
 *    - 把每次遞迴呼叫的參數 (n, from, to, aux) 存入 Stack
 *    - 用 while 迴圈 pop + 處理
 * ============================================================================ */

// 遞迴版
void hanoiRec(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "  Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoiRec(n - 1, from, aux, to);     // 上面 n-1 個搬到 aux
    cout << "  Move disk " << n << " from " << from << " to " << to << endl;
    hanoiRec(n - 1, aux, to, from);     // n-1 個從 aux 搬到 to
}

// 非遞迴版 — 手動 Stack 模擬
// Stack 中的每個 frame 記錄：(n, from, to, aux, phase)
// phase 0: 尚未處理第一個遞迴呼叫
// phase 1: 第一個遞迴完成，該移動盤子了
// phase 2: 該處理第二個遞迴呼叫了
struct HanoiFrame {
    int n;
    char from, to, aux;
    int phase;
};

void hanoiIter(int n, char from, char to, char aux) {
    stack<HanoiFrame> s;
    s.push({n, from, to, aux, 0});

    while (!s.empty()) {
        HanoiFrame& f = s.top();

        if (f.n == 1) {
            // Base case: 直接移動
            cout << "  Move disk 1 from " << f.from << " to " << f.to << endl;
            s.pop();
            continue;
        }

        if (f.phase == 0) {
            // 第一步：把上面 n-1 個從 from 搬到 aux（使用 to 作輔助）
            f.phase = 1;
            s.push({f.n - 1, f.from, f.aux, f.to, 0});
        } else if (f.phase == 1) {
            // 第二步：移動最大的盤子
            cout << "  Move disk " << f.n << " from " << f.from << " to " << f.to << endl;
            f.phase = 2;
            // 第三步：把 n-1 個從 aux 搬到 to（使用 from 作輔助）
            s.push({f.n - 1, f.aux, f.to, f.from, 0});
        } else {
            // phase == 2: 所有子任務完成
            s.pop();
        }
    }
}

/* ============================================================================
 *  8. 二元樹 Inorder 遍歷
 *
 *  轉換方法：【手動 Stack 模擬】
 *    - 先沿左邊一路往下 push
 *    - pop 時訪問節點
 *    - 然後轉向右子樹
 * ============================================================================ */
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : data(v), left(nullptr), right(nullptr) {}
};

// 輔助：插入到 BST
TreeNode* bstInsert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->data)  root->left  = bstInsert(root->left, val);
    else if (val > root->data) root->right = bstInsert(root->right, val);
    return root;
}

// 遞迴版 Inorder: Left → Root → Right
void inorderRec(TreeNode* node) {
    if (!node) return;
    inorderRec(node->left);
    cout << node->data << " ";
    inorderRec(node->right);
}

// 非遞迴版 Inorder — 手動 Stack
// 模擬 call stack 的行為
void inorderIter(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;

    while (cur != nullptr || !s.empty()) {
        // 一路往左走到底，沿途 push 所有節點
        while (cur != nullptr) {
            s.push(cur);
            cur = cur->left;
        }
        // pop 最左的節點 → 訪問它
        cur = s.top();
        s.pop();
        cout << cur->data << " ";
        // 轉向右子樹
        cur = cur->right;
    }
}

// 非遞迴版 Preorder — 手動 Stack (Root → Left → Right)
void preorderIter(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* cur = s.top();
        s.pop();
        cout << cur->data << " ";
        // 先 push 右再 push 左（因為 stack 是 LIFO，左要先被處理）
        if (cur->right) s.push(cur->right);
        if (cur->left)  s.push(cur->left);
    }
}

// 釋放樹
void deleteTree(TreeNode* node) {
    if (!node) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

/* ============================================================================
 *  9. 反轉字串
 *
 *  轉換方法：【雙指標（頭尾交換）】
 * ============================================================================ */

// 遞迴版 — 交換首尾字元，然後遞迴反轉中間
void reverseRec(string& s, int left, int right) {
    if (left >= right) return;         // Base case: 中間沒東西了
    swap(s[left], s[right]);           // 交換首尾
    reverseRec(s, left + 1, right - 1); // 遞迴處理中間
}

// 迭代版 — 雙指標從兩端向中間靠攏
void reverseIter(string& s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        swap(s[left], s[right]);
        ++left;
        --right;
    }
}

/* ============================================================================
 *  10. Quick Sort
 *
 *  轉換方法：【Stack 存待排序的 (low, high) 區間】
 * ============================================================================ */

// Partition: 選最後一個元素為 pivot，把小的放左邊、大的放右邊
int partition(vector<int>& a, int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (a[j] <= pivot) {
            ++i;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

// 遞迴版
void qsRec(vector<int>& a, int low, int high) {
    if (low >= high) return;
    int p = partition(a, low, high);
    qsRec(a, low, p - 1);    // 排序左半
    qsRec(a, p + 1, high);   // 排序右半
}

// 非遞迴版 — Stack 存待排序區間
void qsIter(vector<int>& a, int low, int high) {
    stack<pair<int, int>> s;
    s.push({low, high});

    while (!s.empty()) {
        auto range = s.top();
        s.pop();
        int lo = range.first;
        int hi = range.second;

        if (lo >= hi) continue;

        int p = partition(a, lo, hi);
        // push 兩個子區間（順序無所謂，Stack 會反過來處理）
        s.push({lo, p - 1});
        s.push({p + 1, hi});
    }
}

/* ============================================================================
 *  主程式
 * ============================================================================ */
int main() {
    cout << "============================================================" << endl;
    cout << "  遞迴 vs 非遞迴（迭代）完整範例" << endl;
    cout << "============================================================\n" << endl;

    // ── 1. 階乘 ──
    cout << "【1. Factorial 階乘】" << endl;
    int n = 10;
    cout << "  factorialRec(" << n << ")  = " << factorialRec(n) << endl;
    cout << "  factorialIter(" << n << ") = " << factorialIter(n) << endl;
    cout << "  factorialTail(" << n << ") = " << factorialTail(n) << endl;
    cout << endl;

    // ── 3. Fibonacci ──
    cout << "【3. Fibonacci】" << endl;
    n = 20;
    cout << "  fibRec(" << n << ")  = " << fibRec(n) << "  [O(2^N) — 慢]" << endl;
    cout << "  fibIter(" << n << ") = " << fibIter(n) << "  [O(N)]" << endl;

    // 4. Memoization
    n = 40;
    memo.assign(n + 1, -1);
    cout << "  fibMemo(" << n << ") = " << fibMemo(n) << "  [O(N) with memo]" << endl;
    cout << "  fibIter(" << n << ") = " << fibIter(n) << "  [O(N)]" << endl;
    cout << endl;

    // ── 5. Binary Search ──
    cout << "【5. Binary Search 二元搜尋】" << endl;
    vector<int> sorted = {2, 5, 8, 11, 14, 17, 20, 23, 26, 29};
    cout << "  Array: ";
    for (int x : sorted) cout << x << " ";
    cout << endl;
    int target = 17;
    cout << "  bsRec(target=" << target << ")  = index " << bsRec(sorted, 0, (int)sorted.size() - 1, target) << endl;
    cout << "  bsIter(target=" << target << ") = index " << bsIter(sorted, target) << endl;
    target = 99;
    cout << "  bsRec(target=" << target << ")  = index " << bsRec(sorted, 0, (int)sorted.size() - 1, target) << endl;
    cout << "  bsIter(target=" << target << ") = index " << bsIter(sorted, target) << endl;
    cout << endl;

    // ── 6. GCD ──
    cout << "【6. GCD 最大公因數】" << endl;
    cout << "  gcdRec(1989, 1590)  = " << gcdRec(1989, 1590) << endl;
    cout << "  gcdIter(1989, 1590) = " << gcdIter(1989, 1590) << endl;
    cout << endl;

    // ── 7. 河內塔 ──
    cout << "【7. Tower of Hanoi 河內塔 (n=3)】\n" << endl;
    cout << "  遞迴版:" << endl;
    hanoiRec(3, 'A', 'C', 'B');
    cout << "\n  非遞迴版（手動 Stack）:" << endl;
    hanoiIter(3, 'A', 'C', 'B');
    cout << endl;

    // ── 8. 二元樹 Inorder ──
    cout << "【8. Binary Tree Inorder 遍歷】" << endl;
    TreeNode* tree = nullptr;
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    for (int v : vals) tree = bstInsert(tree, v);
    /*
     *         50
     *        /  \
     *      30    70
     *     / \   / \
     *   20  40 60  80
     */
    cout << "  遞迴 Inorder:    ";
    inorderRec(tree);
    cout << endl;
    cout << "  非遞迴 Inorder:  ";
    inorderIter(tree);
    cout << endl;
    cout << "  非遞迴 Preorder: ";
    preorderIter(tree);
    cout << endl;
    deleteTree(tree);
    cout << endl;

    // ── 9. 反轉字串 ──
    cout << "【9. Reverse String 反轉字串】" << endl;
    string s1 = "Hello, World!";
    string s2 = s1;
    reverseRec(s1, 0, (int)s1.size() - 1);
    reverseIter(s2);
    cout << "  原始:        \"Hello, World!\"" << endl;
    cout << "  遞迴反轉:    \"" << s1 << "\"" << endl;
    cout << "  迭代反轉:    \"" << s2 << "\"" << endl;
    cout << endl;

    // ── 10. Quick Sort ──
    cout << "【10. Quick Sort 快速排序】" << endl;
    vector<int> arr1 = {38, 27, 43, 3, 9, 82, 10};
    vector<int> arr2 = arr1;
    cout << "  原始: ";
    for (int x : arr1) cout << x << " ";
    cout << endl;

    qsRec(arr1, 0, (int)arr1.size() - 1);
    cout << "  遞迴 QS: ";
    for (int x : arr1) cout << x << " ";
    cout << endl;

    qsIter(arr2, 0, (int)arr2.size() - 1);
    cout << "  非遞迴 QS: ";
    for (int x : arr2) cout << x << " ";
    cout << endl;

    cout << "\n============================================================" << endl;
    cout << "  所有範例完成。" << endl;
    cout << "============================================================" << endl;

    return 0;
}