Edited at

C#で階乗の計算(再帰処理)

More than 1 year has passed since last update.


階乗の定義

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で公開したものを加筆・修正したものです。