Help us understand the problem. What is going on with this article?

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

gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2020 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』
https://github.com/gushwell
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away