โปรแกรม C++ คำนวณเลขยกกำลัง (Power) แบบ Recursive และ Non-Recursive

กำลัง x^y โดย x = base, y = exponent

ตัวอย่าง: 2^10 = 1024

1. Non-Recursive (Iterative)

#include <iostream>
using namespace std;

int power(int x, int y) {
    int i, power = 1;
    if(y == 0)
        return 1;
    for(i=1; i<=y; i++)
        power = power * x;
    return power;
}

int main() {
    int x = 3, y = 4;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
    cout << "x^y = " << power(x, y);
    return 0;
}

ผลลัพธ์

x = 3
y = 4
x^y = 81

อธิบาย

int power(int x, int y) {
    int i, power = 1;
    if(y == 0) return 1;
    for(i=1; i<=y; i++)
        power = power * x;
    return power;
}

for loop คูณ x จำนวน y ครั้ง = x^y

2. Recursive (แบ่งครึ่ง Exponent - Fast Exponentiation)

#include <iostream>
using namespace std;

int power(int x, int y) {
    if (y == 0)
        return 1;
    else if (y % 2 == 0)
        return power(x, y/2) * power(x, y/2);
    else
        return x * power(x, y/2) * power(x, y/2);
}

int main() {
    int x = 3, y = 4;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
    cout << "x^y = " << power(x, y);
    return 0;
}

ผลลัพธ์

x = 3
y = 4
x^y = 81

อธิบาย Recursive แบบเร็ว (O(log n))

int power(int x, int y) {
    if (y == 0) return 1;
    else if (y % 2 == 0)
        return power(x, y/2) * power(x, y/2);
    else
        return x * power(x, y/2) * power(x, y/2);
}

• y == 0 → 1
• y เป็นคู่ → (x^(y/2))^2 = power(x, y/2) * power(x, y/2)
• y เป็นคี่ → x × (x^(y/2))^2
• ลดจำนวนการเรียกซ้ำจาก O(n) เป็น O(log n)

main() แสดง x, y, x^y เหมือนกันทั้ง 2 วิธี