C語言實作：遞迴計算冪次（分治法優化 m^n）

遞迴冪次計算：分治法優化

本程式實作遞迴函數 recursion(m, n) 計算 m^n，採用分治策略：
- n=1 回傳 m
- n=2 回傳 m*m
- n 為偶數：m^n = m^(n-2) × m²
- n 為奇數：m^n = m^(n-1) × m

完整程式碼

#include <stdio.h>

int recursion(int m, int n);

int main()
{
    int m, n, result;

    printf("please enter m=");
    scanf("%d", &m);
    printf("please enter n=");
    scanf("%d", &n);

    result = recursion(m, n);
    printf("%d^%d==%d\n", m, n, result);

    return 0;
}

int recursion(int m, int n)
{
    int sum;
    if(n == 1) sum = m;
    else if(n == 2) sum = m * m;
    else
    {
        if(n % 2 == 0)
            sum = recursion(m, n-2) * recursion(m, 2);
        else
            sum = recursion(m, n-1) * recursion(m, 1);
    }
    return sum;
}

執行結果示意

效能分析與問題

嚴重缺陷：重複計算導致指數級複雜度
以 recursion(m, 6) 為例：
recursion(m,6) = recursion(m,4) × recursion(m,2)
recursion(m,4) = recursion(m,2) × recursion(m,2)
recursion(m,2) 被計算了 3 次！
時間複雜度接近 O(2^n)，極度低效。

正確分治法：快速冪演算法 O(log n)

long long power(long long m, int n)
{
    if(n == 0) return 1;
    long long half = power(m, n/2);
    if(n % 2 == 0) return half * half;
    else return half * half * m;
}

或迭代版：

long long power(long long m, int n)
{
    long long result = 1;
    while(n > 0)
    {
        if(n & 1) result *= m;
        m *= m;
        n >>= 1;
    }
    return result;
}

比較表

教學重點

• 分治法核心：將問題分解為**不重疊**的子問題。
• 原始碼錯誤示範：子問題重疊導致效率災難。
• 動態規劃/備忘錄可修復重複計算，但快速冪更優雅。
• 整數冪次溢位快，實務建議用 long long 或大整數庫。