সংখ্যার ঘাত (Power) বের করার C++ প্রোগ্রাম (রিকার্সিভ ও নন-রিকার্সিভ)

x^y = x কে y বার নিজের সাথে গুণ। রিকার্সিভ এবং নন-রিকার্সিভ (ইটারেটিভ) দুটি পদ্ধতি।

১. নন-রিকার্সিভ (ইটারেটিভ) পদ্ধতি

#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

২. রিকার্সিভ পদ্ধতি (Exponentiation by Squaring)

#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

ব্যাখ্যা

নন-রিকার্সিভ

সিম্পল লুপ: power *= x y বার।
টাইম: O(y)।

রিকার্সিভ (Exponentiation by Squaring)

y == 0 → 1।
y জোড় হলে: power(x, y/2)^2।
y বিজোড় হলে: x * power(x, y/2)^2।
টাইম: O(log y) — খুব দ্রুত।

নোট: রিকার্সিভ ভার্সনে একই সাব-প্রব্লেম (power(x, y/2)) দুবার কল হয়েছে। এটি অপ্টিমাইজ করতে একটি ভেরিয়েবলে স্টোর করা উচিত: int half = power(x, y/2); return half * half;।