C語言遞迴實作冪函數 n^k：基礎情況 k=0 返回 1

遞迴定義

pow(n, k) = n * pow(n, k-1) (k>0)
pow(n, 0) = 1

標準遞迴

int power(int n, int k) {
    if (k == 0) return 1;
    return n * power(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)

快速冪 O(log k) (遞迴/迭代)

int power_fast(int n, int k) {
    if (k == 0) return 1;
    int half = power_fast(n, k/2);
    if (k % 2 == 0) return half * half;
    return half * half * n;
}

主程式測試

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%d\n", power(n, k));
    return 0;
}