C#｜再帰関数

再帰関数の備忘録です。
階乗を求める再帰関数を書いてみます。

そもそも階乗とは

nの階乗は、1からnまでのすべての整数の積です。
n!のようにあらわします。
例えば、5の階乗はこんな感じです。

5! = 1 * 2 * 3 * 4 * 5

// 120

まずはfor文で

比較のためにまずはfor文で書きます。

static void Main()
{
    Console.WriteLine(factorial(5));  // => 120
}

static int factorial(int n)
{
    int result = 1;

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

    return result;
}

再帰関数で

続いて再帰関数で書くと、こうなります。

static void Main()
{
    Console.WriteLine(factorial(5));  // => 120
}

static int factorial(int n)
{
    // nが1になったら終了
    if (n == 1) return 1;

    // factorialを再帰呼び出し
    return n * factorial(n - 1);
}

実行される順番はこんな感じです。

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 

これの重複部分を省略していくと・・・

factorial(5) = 5 * 4 * 3 * 2 * 1

階乗の計算になります。 終了条件を書き忘れるとループになってしまうので要注意です。