recursion.cpp

// ============================================================
// Ch04 — 遞迴（Recursion）
// 編譯：g++ -std=c++17 -Wall -o recursion recursion.cpp
// ============================================================

#include <iostream>
#include <vector>

// ── 函式原型 ──────────────────────────────────────

// 階乘
long long factorialRecursive(int n);
long long factorialIterative(int n);

// 費波那契
long long fibRecursive(int n);
long long fibIterative(int n);

// 陣列加總
int sumArray(const int arr[], int size);

// 次方
double power(double base, int exponent);

// 二分搜尋
int binarySearch(const std::vector<int>& arr, int target, int low, int high);

// ── 主程式 ────────────────────────────────────────
int main() {
    std::cout << "===== Ch04：遞迴 =====\n\n";

    // ── 1. 階乘（Factorial） ──
    std::cout << "【1】階乘（Factorial）\n";
    std::cout << "遞迴定義：n! = n × (n-1)!\n";
    std::cout << "基底情況：0! = 1, 1! = 1\n\n";

    for (int i = 0; i <= 10; i++) {
        std::cout << i << "! = " << factorialRecursive(i) << "\n";
    }

    std::cout << "\n迭代 vs 遞迴結果比較：\n";
    for (int i = 0; i <= 10; i++) {
        long long rec = factorialRecursive(i);
        long long iter = factorialIterative(i);
        std::cout << i << "! : 遞迴=" << rec
                  << ", 迭代=" << iter
                  << (rec == iter ? " ✓" : " ✗") << "\n";
    }
    std::cout << "\n";

    // ── 2. 費波那契（Fibonacci） ──
    std::cout << "【2】費波那契數列（Fibonacci）\n";
    std::cout << "定義：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)\n\n";

    std::cout << "前 15 項（遞迴）：\n";
    for (int i = 0; i < 15; i++) {
        std::cout << "F(" << i << ") = " << fibRecursive(i) << "\n";
    }

    std::cout << "\n迭代 vs 遞迴結果比較：\n";
    for (int i = 0; i < 15; i++) {
        long long rec = fibRecursive(i);
        long long iter = fibIterative(i);
        std::cout << "F(" << i << ") : 遞迴=" << rec
                  << ", 迭代=" << iter
                  << (rec == iter ? " ✓" : " ✗") << "\n";
    }
    std::cout << "\n";

    // ── 3. 陣列加總 ──
    std::cout << "【3】遞迴陣列加總\n";
    int data[] = {3, 7, 1, 9, 4, 6, 2};
    int dataSize = sizeof(data) / sizeof(data[0]);

    std::cout << "陣列：";
    for (int i = 0; i < dataSize; i++) {
        std::cout << data[i] << " ";
    }
    std::cout << "\n";

    std::cout << "加總結果：" << sumArray(data, dataSize) << "\n\n";

    // ── 4. 次方（Power） ──
    std::cout << "【4】遞迴次方計算\n";
    std::cout << "2^10 = " << power(2.0, 10) << "\n";
    std::cout << "3^5  = " << power(3.0, 5) << "\n";
    std::cout << "5^0  = " << power(5.0, 0) << "\n";
    std::cout << "2^-3 = " << power(2.0, -3) << "\n\n";

    // ── 5. 二分搜尋（Binary Search） ──
    std::cout << "【5】遞迴二分搜尋\n";
    std::vector<int> sorted = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};

    std::cout << "已排序陣列：";
    for (int v : sorted) {
        std::cout << v << " ";
    }
    std::cout << "\n\n";

    int targets[] = {23, 72, 1, 56, 100};
    for (int target : targets) {
        int result = binarySearch(sorted, target, 0,
                                  static_cast<int>(sorted.size()) - 1);
        if (result != -1) {
            std::cout << "搜尋 " << target << " → 找到，索引 = " << result << "\n";
        } else {
            std::cout << "搜尋 " << target << " → 找不到\n";
        }
    }
    std::cout << "\n";

    // ── 6. 遞迴 vs 迭代的取捨 ──
    std::cout << "【6】遞迴 vs 迭代的取捨\n";
    std::cout << "┌────────────┬──────────────────┬──────────────────┐\n";
    std::cout << "│   比較項目  │      遞迴         │      迭代        │\n";
    std::cout << "├────────────┼──────────────────┼──────────────────┤\n";
    std::cout << "│ 程式可讀性  │ 通常較直觀         │ 可能較冗長        │\n";
    std::cout << "│ 記憶體用量  │ 使用堆疊，較多      │ 通常較少          │\n";
    std::cout << "│ 效能       │ 函式呼叫有額外開銷   │ 通常較快          │\n";
    std::cout << "│ 溢位風險   │ 可能堆疊溢位        │ 無此風險          │\n";
    std::cout << "│ 適用場景   │ 樹、圖走訪、分治法   │ 簡單迴圈問題       │\n";
    std::cout << "└────────────┴──────────────────┴──────────────────┘\n";

    return 0;
}

// ── 函式定義 ──────────────────────────────────────

// 階乘（遞迴版本）
// 基底情況：n <= 1 回傳 1
// 遞迴情況：n * factorial(n-1)
long long factorialRecursive(int n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

// 階乘（迭代版本）
long long factorialIterative(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

// 費波那契（遞迴版本）
// 注意：時間複雜度 O(2^n)，僅適合小數值
long long fibRecursive(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// 費波那契（迭代版本）— 時間複雜度 O(n)
long long fibIterative(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;

    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

// 陣列加總（遞迴）
// 基底情況：size == 0 回傳 0
// 遞迴情況：最後一個元素 + 前面所有元素的加總
int sumArray(const int arr[], int size) {
    if (size <= 0) return 0;
    return arr[size - 1] + sumArray(arr, size - 1);
}

// 次方計算（遞迴）— 支援負指數
double power(double base, int exponent) {
    if (exponent == 0) return 1.0;
    if (exponent < 0) return 1.0 / power(base, -exponent);
    return base * power(base, exponent - 1);
}

// 二分搜尋（遞迴）
// 前提：陣列必須已排序
int binarySearch(const std::vector<int>& arr, int target, int low, int high) {
    if (low > high) return -1;  // 基底情況：找不到

    int mid = low + (high - low) / 2;  // 避免整數溢位

    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearch(arr, target, low, mid - 1);
    return binarySearch(arr, target, mid + 1, high);
}