C#で再帰呼び出しを使って任意の数の累乗を効率的に求める方法

この記事では、C#を使用して再帰呼び出し（バックトラッキング）によって任意の数の累乗を計算する方法を解説します。

アルゴリズムの考え方

まず、基数 x と指数 n を引数に取る FindPower 関数を作成します。ここでは x = 2、n = 累乗する回数とします。

処理の流れは以下の通りです。

• n が 0 になったら 1 を返す（再帰の終了条件）
• n を半分にして再帰的に自分自身を呼び出す
• n が偶数の場合：result × result を返す
• n が奇数の場合：x × result × result を返す

この手法では、毎回 x を掛ける代わりに結果を二乗しながら再帰を進めるため、通常のループによる計算（O(n)）よりも少ない計算量（O(log n)）で累乗を求められます。

具体例

例えば、2 の 8 乗を求める場合を考えてみましょう。

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 ＝ 256

再帰的には、2⁸ → 2⁴ → 2² → 2¹ と指数を半分ずつ減らしながら、各段階で結果を二乗していくことで効率的に計算できます。

C#での実装例

using System;
namespace ConsoleApplication{
    public class BackTracking{
        public int FindPower(int x, int n){
            int result;
            if (n == 0){
                return 1;
            }
            result = FindPower(x, n / 2);
            if (n % 2 == 0){
                return result * result;
            }
            else{
                return x * result * result;
            }
        }
    }
    class Program{
        static void Main(string[] args){
            BackTracking b = new BackTracking();
            int res = b.FindPower(2, 8);
            Console.WriteLine(res);
        }
    }
}

実行結果

256

コードの解説

• 終了条件： n == 0 のときに 1 を返します。これにより再帰呼び出しが正しく終了します。
• 再帰ステップ： FindPower(x, n / 2) を呼び出し、問題のサイズを半分に縮小します。
• 偶数の場合： 半分の結果を二乗するだけで答えが得られます。
• 奇数の場合： 二乗した結果にさらに x を掛けて補正します。

このように、再帰と二乗の組み合わせを利用することで、大きな指数を持つ累乗計算も高速に処理できます。ぜひ自分のコードにも応用してみてください。