Chương trình C tính x^mũ n bằng hàm đệ quy

Tính x^n (x, n nhập từ bàn phím) dùng hàm đệ quy tối ưu: nếu n chẵn, x^n = (x^(n/2))^2; nếu n lẻ, x^n = x * x^(n-1). Cơ sở: n=1 trả về x.

Giải thuật

• power(x, n): if n==1 return x; else if n%2==0 return pow(power(x,n/2),2); else return x*power(x,n-1)
• Độ phức tạp O(log n) nhờ chia đôi khi n chẵn

Chương trình

#include <stdio.h>
#include <math.h>

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

void main() {
    long int x, n, xpown;
    printf("Enter X and N: "); scanf("%ld %ld", &x, &n);
    xpown = power(x, n);
    printf("X^N = %ld\n", xpown);
}

Kết quả

X=5, N=4 → 625