C#で階乗の計算（再帰処理）

階乗の定義

nの階乗とは、1からnまでの整数の積です。nの階乗をn!と表すと、

n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1    (n > 0 のとき)
   = 1                                      (n = 0 のとき)

と表せます。n = 0 の時は、0!は、定義上1とします。

n > 0 の場合を考えると、

(n-1) * (n-2) * ... *  3 * 2 * 1

の部分は、 (n-1)! を計算していることになりますから、

n! = n * (n-1)!

となります。

つまり、以下のように定義できます。

n! = n * (n-1)!    (n > 0 のとき)
   = 1             (n = 0 のとき)

C#での階乗の計算

上の定義を素直にC#のコードで記述したのが、以下のFactorialメソッドです。

Factorial.cs

public static long Factorial(int n) {
    if (n == 0)
        return 1L;
    return n * Factorial(n - 1);
}

Factorialメソッドの中で、Factorialメソッドを呼び出しています。つまり再帰処理を行っています。

C#6.0の機能を使うと、以下のようにも書けます。

Factorial60.cs

static long Factorial(int n) =>
    n == 0 ? 1L : n * Factorial(n - 1);

オーバーフローを検知する

コメント欄のshiracamusさんがお示しになったようなコードでオーバーフローを検知する方法をもありますが、以下のように書けば、オーバーフロー時にOverflowException例外が発生するようになります。

public static long Factorial(int n) {
    checked {
        if (n == 0)
            return 1L;
        return n * Factorial(n - 1);
    }
}

GitHubで上記コードを公開しています。

C#6.0の機能を使うと以下のようにかけます。

static long Factorial(int n) =>
    checked (n == 0 ? 1L : n * Factorial(n - 1));

---

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。