C語言遞歸實現冪函數 n^k：my_pow 完整代碼

C語言遞歸實現冪函數 n^k：my_pow 完整代碼

遞歸計算 n 的 k 次方。基線條件 k=0 返回 1，遞歸關係 n^k = n × n^{k-1}。

遞歸實現

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

int my_pow(int n, int k) {
    if (k == 0) return 1;
    return n * my_pow(n, k - 1);
}

int main() {
    int n, k;
    printf("輸入底數 n 和指數 k：");
    scanf("%d %d", &n, &k);
    printf("%d^%d = %d\n", n, k, my_pow(n, k));
    system("pause");
    return 0;
}

遞歸執行過程 (2^5)

my_pow(2, 5)
= 2 * my_pow(2, 4)
= 2 * 2 * my_pow(2, 3)
= 2 * 2 * 2 * my_pow(2, 2)
= 2 * 2 * 2 * 2 * my_pow(2, 1)
= 2 * 2 * 2 * 2 * 2 * my_pow(2, 0)
= 2 * 2 * 2 * 2 * 2 * 1
= 32

優化：快速冪（分治遞歸，O(log k)）

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

遞歸深度從 k 降為 log₂k，大指數極其高效。

迭代版對比

int pow_iter(int n, int k) {
    int result = 1;
    while (k--) result *= n;
    return result;
}

總結