C++で再帰を使って累乗を計算する方法【サンプルコード付き】

数の累乗は x^y の形式で表されます。ここで、x は基数（元の数）、y は指数（べき乗する回数）です。

例えば、以下のような計算になります。

x = 2、y = 10 の場合
x^y = 1024
つまり、2^10 = 1024 となります

この累乗は、再帰（リカージョン）を使うことで簡潔に求めることができます。以下に、再帰を利用して累乗を計算するC++プログラムを紹介します。

サンプルコード

#include <iostream>
using namespace std;
int FindPower(int base, int power) {
    if (power == 0)
    return 1;
    else
    return (base * FindPower(base, power-1));
}
int main() {
    int base = 3, power = 5;
    cout<<base<<" raised to the power "<<power<<" is "<<FindPower(base, power);
    return 0;
}

実行結果

3 raised to the power 5 is 243

プログラムの解説

上記のプログラムでは、FindPower() 関数が再帰関数として実装されています。処理の流れは以下のとおりです。

• 指数が 0 の場合： 任意の数の 0 乗は必ず 1 になるため、関数は 1 を返します。これが再帰の終了条件（ベースケース）です。
• 指数が 0 以外の場合： 関数は自分自身を再帰的に呼び出し、指数を 1 ずつ減らしながら計算を繰り返します。

該当するコード部分は以下のとおりです。

int FindPower(int base, int power) {
    if (power == 0)
    return 1;
    else
    return (base * FindPower(base, power-1));
}

そして main() 関数内で最初に FindPower() を呼び出し、その戻り値である累乗の計算結果を出力しています。

再帰の動作の流れ

例として FindPower(3, 5) を呼び出した場合、内部では次のように処理が進みます。

FindPower(3, 5) = 3 * FindPower(3, 4)
FindPower(3, 4) = 3 * FindPower(3, 3)
FindPower(3, 3) = 3 * FindPower(3, 2)
FindPower(3, 2) = 3 * FindPower(3, 1)
FindPower(3, 1) = 3 * FindPower(3, 0)
FindPower(3, 0) = 1

各呼び出しの結果が順に戻されながら掛け合わされ、最終的に 3 × 3 × 3 × 3 × 3 = 243 という答えが得られます。

なお、この再帰による実装の時間計算量は O(n)、空間計算量も呼び出しスタックの深さ分だけ必要となるため O(n) です。より効率化したい場合は、繰り返し処理や「繰り返し二乗法」を用いる方法もあります。