C語言遞歸實現冪函數：n^k 計算與靜態變量陷阱

C語言遞歸實現冪函數：n^k 計算與靜態變量陷阱

遞歸版本代碼

#include <stdio.h>

// 遞歸計算 n^k
int power_recursive(int n, int k) {
    if (k == 0) return 1;          // 基線條件：任何數的 0 次冪為 1
    if (k == 1) return n;          // 基線條件：1 次冪為本身
    return n * power_recursive(n, k - 1); // 遞歸步驟
}

int main() {
    int n, k;
    printf("輸入底數 n 和指數 k: ");
    scanf("%d %d", &n, &k);
    if (k < 0) {
        printf("指數必須為非負整數\n");
        return 1;
    }
    printf("%d^%d = %d\n", n, k, power_recursive(n, k));
    return 0;
}

原文代碼的嚴重缺陷分析

// 原文有問題的版本
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;
}

致命問題：

1. 靜態變量保留狀態：static int num = 1 只在首次調用初始化。後續調用 power_recursive(2,3) 後再調用 power_recursive(3,2) 會基於上次殘留值計算，結果完全錯誤。
2. 非線程安全：多線程調用時數據競爭。
3. 不支持遞歸重入：遞歸調用共享同一 num，中間結果相互覆蓋。
4. 返回值邏輯錯誤：遞歸調用的返回值被忽略，依賴副作用修改全局狀態，違背函數式編程原則。

正確遞歸設計原則

• 無副作用：函數不修改任何外部/靜態狀態，相同輸入必得相同輸出。
• 基線條件明確：k==0 返回 1，k==1 返回 n。
• 遞歸步驟縮小問題：n^k = n * n^(k-1)。
• 尾遞歸優化 (編譯器支持時)：

  int power_tail(int n, int k, int acc) {
      if (k == 0) return acc;
      return power_tail(n, k - 1, acc * n);
  }
  // 調用: power_tail(n, k, 1);

迭代版本 (生產環境推薦)

int power_iterative(int n, int k) {
    int result = 1;
    while (k > 0) {
        if (k & 1) result *= n; // 快速冪優化：二進制分解指數
        n *= n;
        k >>= 1;
    }
    return result;
}

時間複雜度 O(log k)，無棧溢出風險，效率最高。