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

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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした