C語言遞迴實作冪函數 n^k（含靜態變數陷阱分析）

原始碼問題分析

int number_power(const int n, int k) {
    static int num = 1; // 靜態區域變數：生命週期贯穿整個程式，僅初始化一次！
    num = num * n;
    if (k > 1) { k--; number_power(n, k); }
    return num;
}

嚴重缺陷：static int num = 1 導致：

1. 首次呼叫 number_power(2,3) 回傳 8 (正確)。
2. 第二次呼叫 number_power(3,2)，num 保留上次值 8 → 計算 8*3*3=72 (錯誤，應為 9)。
3. 執行緒不安全，無法重入。

正確遞迴寫法（純函式、無副作用）

// 尾遞迴優化友善
long long power_recursive(int n, int k) {
    if (k == 0) return 1;
    if (k == 1) return n;
    long long half = power_recursive(n, k / 2);
    if (k % 2 == 0) return half * half;
    else return half * half * n;
}

// 或簡單版（教學用）
int power_simple(int n, int k) {
    if (k == 0) return 1;
    return n * power_simple(n, k - 1);
}

關鍵差異對照

快速冪 迭代版（工程首選，無堆疊溢位風險）

long long power_iterative(int n, int k) {
    long long result = 1;
    long long base = n;
    while (k > 0) {
        if (k & 1) result *= base;
        base *= base;
        k >>= 1;
    }
    return result;
}

總結

• 遞迴必須無副作用，避免 static/全域變數污染狀態。
• 快速冪 O(log k) 為大指數標準解法。
• 工程上優先用迭代版，避免深遞迴堆疊溢位。