C++で数値の累乗を計算する方法：再帰・非再帰プログラムの実装例

数の累乗とは

数の累乗は x^y の形式で表され、x は基数（底）、y は指数を表します。

例を見てみましょう。

x = 2、y = 10 の場合
    x^y = 1024
    ここで、x^y は 2^10 を意味します

数の累乗は、再帰的プログラムと非再帰的プログラムの2つの方法で計算できます。以下、それぞれの実装方法を詳しく解説します。

非再帰プログラムによる累乗の計算

まずは、forループを使用した非再帰的なプログラムの例です。

サンプルコード

#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;
    int 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() 関数を使用しています。この関数は非再帰的（反復的）な関数です。

関数内では、1 から y まで実行される for ループが使われており、ループの各反復ごとに x が power 変数に掛けられていきます。

つまり、x を y 回掛け合わせた結果が power に格納され、これにより x^y の値が求められます。最後に、その結果が main() 関数に返されます。

以下のコードスニペットで、この処理を確認できます。

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

main() 関数では、x、y、x^y の値が表示されます。

cout<<"x = "<<x<<endl;
cout<<"y = "<<y<<endl;
cout<<"x^y = "<<power(x, y);

再帰プログラムによる累乗の計算

次に、再帰呼び出しを利用したプログラムの例を紹介します。この方法では、指数を半分ずつ分割していくことで、効率的に計算を行います。

サンプルコード

#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;
    int 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() が再帰関数として実装されています。処理の流れは以下のとおりです。

• y が 0 の場合： 1 を返します（累乗の基本ケース）。
• y が偶数の場合： x と y/2 を引数として自分自身を再帰的に呼び出し、power(x, y/2) * power(x, y/2) を返します。
• y が奇数の場合： x と y/2 を引数として自分自身を再帰的に呼び出し、x * power(x, y/2) * power(x, y/2) を返します。

以下のコードスニペットで、この再帰処理を確認できます。

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

main() 関数では、x、y、x^y の値が表示されます。

cout<<"x = "<<x<<endl;
cout<<"y = "<<y<<endl;
cout<<"x^y = "<<power(x, y);

両者の計算量の違い

非再帰プログラムは指数 y の回数だけループを実行するため、計算量は O(n) です。一方、再帰プログラムは指数を半分ずつ分割して計算するため、計算量は O(log n) となり、大きな指数を扱う場合により効率的です。

ただし、上記の再帰実装では power(x, y/2) を2回呼び出しているため、実際には同じ計算が重複して行われます。実務では、結果を一時変数に保存して1回の呼び出しにまとめることで、真の O(log n) を実現できます。

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

このように、C++では目的や規模に応じて非再帰・再帰のいずれかの方法を選択することで、効率的に累乗計算を行うことができます。