【C#】階乗計算のサンプルで考える再帰関数（メソッド）

2023年10月20日2023年10月21日

メソッドブロック内で自分が実行しているメソッド自体を呼び出すことを再帰関数と呼びます

頻繁に使うものではありませんが、学習とメソッドの理解を深めるための経験をしておくのがいいですね

階乗とは

階乗（かいじょう、英: factorial）は、非負整数に対して定義される数学的な演算です。階乗は通常、感嘆符「!」を用いて表されます。nの階乗は、n!と書き表され、次のように定義されます

n! = n × (n – 1) × (n – 2) × … × 2 × 1

例えば、5の階乗は以下のように計算できます：

5! = 5 × 4 × 3 × 2 × 1 = 120

階乗は組み合わせ論や確率論など、数学や統計学の様々な分野で使用されます。また、階乗は順列や組み合わせの計算において重要な役割を果たします。階乗を計算する際には、0の階乗は1と定義されます。

階乗の計算は簡単な整数の掛け算を用いて行えますが、大きな整数に対しては非常に急速に増加するため、大きな数の階乗を計算する場合にはコンピュータプログラムを用いることが一般的です。

シンプルで実用的なコードを導くと

C#のコードで書くと次のようになるでしょうか

Console.WriteLine($"5の階乗は{5 * 4 * 3 * 2 * 1}です。");

５の階乗に限らずnの階乗を求めるコードを書いてみましょう

int n = 5; // nの値を変更することができます

int factorial = 1;

for (int i = 1; i <= n; i++)
{
    factorial *= i;
}

Console.WriteLine($"{n}の階乗は{factorial}です。");

再帰関数（メソッド）の学習のため、思考実験的に考えてみましょう

メソッドを呼び出すように変更

冗長にはなりますが、学習のために展開してみます

冗長（冗長」（じょうちょう、英: redundancy）は、何かが余分であること、または必要以上に繰り返されていることを指す言葉です。この用語は、さまざまな文脈で使用されます。）

５つのメソッドを作成し、それぞれが数値を返すものとします

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5();
int result4 = CalculateFactorial4();
int result3 = CalculateFactorial3();
int result2 = CalculateFactorial2();
int result1 = CalculateFactorial1();

Console.WriteLine($"{n}の階乗は{result1 * result2 * result3 * result4 * result5}です。");

int CalculateFactorial5()
{
    return 5;
}

int CalculateFactorial4()
{
    return 4;
}

int CalculateFactorial3()
{
    return 3;
}

int CalculateFactorial2()
{
    return 2;
}

int CalculateFactorial1()
{
    return 1;
}

CalculateFactorial5()メソッドを更新します

CalculateFactorial5()メソッドでCalculateFactorial4()メソッドを呼び出すコードを記述します

int CalculateFactorial5()
{
    return 5 * CalculateFactorial4();
}

このブロックで、CalculateFactorial4()を呼び出すことで、次の行が省略できることを確認しましょう

// このコード自体が省略できますね
int result4 = CalculateFactorial4(); 

// 同じくresult4が省略できます
Console.WriteLine($"{n}の階乗は{result1 * result2 * result3 * result5}です。");

更新した全体のコード

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5();
// int result4 = CalculateFactorial4();
int result3 = CalculateFactorial3();
int result2 = CalculateFactorial2();
int result1 = CalculateFactorial1();

Console.WriteLine($"{n}の階乗は{result1 * result2 * result3 * result5}です。");

int CalculateFactorial5()
{
    return 5 * CalculateFactorial4();
}

int CalculateFactorial4()
{
    return 4;
}

int CalculateFactorial3()
{
    return 3;
}

int CalculateFactorial2()
{
    return 2;
}

int CalculateFactorial1()
{
    return 1;
}

メソッドからメソッドを呼び出す

実際は、アドレス以外にも引数やローカル変数などもスタックに積まれます

Retuenで呼び出し元に戻る

全てのメソッドに変更を反映させてみましょう

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5();
// int result4 = CalculateFactorial4();
// int result3 = CalculateFactorial3();
// int result2 = CalculateFactorial2();
// int result1 = CalculateFactorial1();

Console.WriteLine($"{n}の階乗は{result5}です。");

int CalculateFactorial5()
{
    return 5 * CalculateFactorial4();
}

int CalculateFactorial4()
{
    return 4 * CalculateFactorial3();
}

int CalculateFactorial3()
{
    return 3 * CalculateFactorial2();
}

int CalculateFactorial2()
{
    return 2 * CalculateFactorial1();
}

int CalculateFactorial1()
{
    return 1;
}

メソッド内の数値のところを変数に置き換える

CalculateFactorial5()メソッドに引数を渡して置き換えてみましょう

CalculateFactorial5()をCalculateFactorial5(5)として呼び出してみましょう

CalculateFactorial5(int n)メソッドの部分だけ抜き出したものになります

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5(n);

Console.WriteLine($"{n}の階乗は{result5}です。");

int CalculateFactorial5(int n)
{
    return n * CalculateFactorial4();
}

上のコードを当てはめた全体コード

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5(n);

Console.WriteLine($"{n}の階乗は{result5}です。");

int CalculateFactorial5(int n)
{
    return n * CalculateFactorial4();
}

int CalculateFactorial4()
{
    return 4 * CalculateFactorial3();
}

int CalculateFactorial3()
{
    return 3 * CalculateFactorial2();
}

int CalculateFactorial2()
{
    return 2 * CalculateFactorial1();
}

int CalculateFactorial1()
{
    return 1;
}

CalculateFactorial4()メソッドも更新してみましょう

CalculateFactorial4()メソッドを同じく引数ありに更新していきます

int CalculateFactorial4(int n)
{
    return n * CalculateFactorial3();
}

CalculateFactorial5(int n)メソッドから呼び出されるときには、nは１減らした値となります
CalculateFactorial5(int n)のnが5なら、n-1を引数にすれば良さそうです

int CalculateFactorial5(int n)
{
    return n * CalculateFactorial4(n - 1);
}

int CalculateFactorial4(int n)
{
    return n * CalculateFactorial3();
}

全てのメソッドのブロックを置き換えてみましょう

同じことを繰り返します
メソッド名以外同じになりましたので、まとめる方法を考えていきます

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5(n);

Console.WriteLine($"{n}の階乗は{result5}です。");

int CalculateFactorial5(int n)
{
    return n * CalculateFactorial4(n - 1);
}

int CalculateFactorial4(int n)
{
    return n * CalculateFactorial3(n - 1);
}

int CalculateFactorial3(int n)
{
    return n * CalculateFactorial2(n - 1);
}

int CalculateFactorial2(int n)
{
    return n * CalculateFactorial1(n - 1);
}

int CalculateFactorial1(int n)
{
    return n;
}

（数学的なルールでの更新）nが0の場合の階乗は１になると決められています

nが0の場合は、数学で1になると決められていますので、考慮してCalculateFactorial0メソッドを最後尾に追加します

int n = 5; // 階乗を計算したい数

int result5 = CalculateFactorial5(n);

Console.WriteLine($"{n}の階乗は{result5}です。");

int CalculateFactorial5(int n)
{
    return n * CalculateFactorial4(n - 1);
}

int CalculateFactorial4(int n)
{
    return n * CalculateFactorial3(n - 1);
}

int CalculateFactorial3(int n)
{
    return n * CalculateFactorial2(n - 1);
}

int CalculateFactorial2(int n)
{
    return n * CalculateFactorial1(n - 1);
}

int CalculateFactorial1(int n)
{
    return n * CalculateFactorial0(n - 1);
}

int CalculateFactorial0(int n)
{
    return 1;
}

上記コードを再帰関数を使ってまとめてみましょう

int n = 5; // 階乗を計算したい数

int result = CalculateFactorial(n);

Console.WriteLine($"{n}の階乗は{result}です。");

static int CalculateFactorial(int n)
{
    if (n == 0)
    {
        return 1; // 0の階乗は1
    }
    return n * CalculateFactorial(n - 1);
}

おまけ

インテリセンスを使って省略してみましょう

int n = 5; // 階乗を計算したい数

int result = CalculateFactorial(n);

Console.WriteLine($"{n}の階乗は{result}です。");

int CalculateFactorial(int n)
{
    return n == 0 ? 1 : n * CalculateFactorial(n - 1);
}

もう一度、やってみましょう

int n = 5; // 階乗を計算したい数

int result = CalculateFactorial(n);

Console.WriteLine($"{n}の階乗は{result}です。");

int CalculateFactorial(int n) => n == 0 ? 1 : n * CalculateFactorial(n - 1);

現実的なリファクタリング例

色々みてきましたが、最終的にはこれに落ち着くでしょう
気を衒って難しく（短く）するより、多くの人が理解しやすい段階に押さえておくのも綺麗なコードを作成するコツですね

using System;

class Program
{
    static void Main()
    {
        int n = 5; // 階乗を計算したい数
        int result = CalculateFactorial(n);

        Console.WriteLine($"{n}の階乗は{result}です.");
    }

    static int CalculateFactorial(int n)
    {
        if (n < 0)
            throw new ArgumentException("負の整数の階乗は計算できません.");

        int factorial = 1;

        for (int i = 1; i <= n; i++)
        {
            factorial *= i;
        }

        return factorial;
    }
}

このリファクタリングでは、再帰を使わずにループを用いて階乗を計算しています。メソッド CalculateFactorial は、引数 n が負の場合に例外をスローするように改良しました。その後、for ループを使用して 1 から n までの整数を順番に掛け合わせて階乗を計算し、その結果を返します。

このコードはより効率的で理解しやすくなり、負の整数が与えられた場合にエラー処理も行います。