โปรแกรม C คำนวณ x ยกกำลัง n ด้วยฟังก์ชัน Recursive

คำอธิบายปัญหา

คำนวณ x^n โดย x และ n รับจากผู้ใช้ ใช้ฟังก์ชัน Recursive เพื่อลดจำนวนการคูณ (Exponentiation by Squaring)

ตรรกะ Recursive

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

อัลกอริทึม

1. Base case: n=1 คืน x
2. n คู่: x^n = (x^(n/2))^2
3. n คี่: x^n = x * x^(n-1)

โค้ดตัวอย่าง

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

long 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);
}

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

ผลลัพธ์

X = 5, N = 4 → 625

หมายเหตุ

วิธีนี้มี Time Complexity O(log n) เร็วกว่าการคูณซ้ำ n-1 ครั้ง (O(n))