C++で再帰を使って数値の階乗を求めるプログラム

階乗とは

非負整数 n の階乗（factorial）とは、n 以下のすべての正の整数を掛け合わせた積のことです。記号「!」を用いて表されます。

例えば、4 の階乗は次のように計算されます。

4! = 4 × 3 × 2 × 1
4! = 24

整数の階乗は、再帰を使ったプログラムでも、繰り返し処理（反復）を使ったプログラムでも求めることができます。

再帰を使った階乗を求めるC++プログラム

以下のプログラムは、再帰処理を用いて数値の階乗を求める例です。

サンプルコード

#include <iostream>
using namespace std;
int fact(int n) {
    if ((n==0)||(n==1))
    return 1;
    else
    return n*fact(n-1);
}
int main() {
    int n = 4;
    cout<<"Factorial of "<<n<<" is "<<fact(n);
    return 0;
}

実行結果

Factorial of 4 is 24

プログラムの解説

上記のプログラムでは、関数 fact() が再帰関数として機能しています。main() 関数は、階乗を求めたい数値を引数に渡して fact() を呼び出します。該当するコードは以下の通りです。

cout<<"Factorial of "<<n<<" is "<<fact(n);

引数が 0 または 1 の場合、fact() は 1 を返します。これが再帰の終了条件（ベースケース）です。それ以外の場合は、引数を n-1 として自分自身を再帰的に呼び出し、その結果に n を掛け合わせた値を返します。

int fact(int n) {
    if ((n==0)||(n==1))
    return 1;
    else
    return n*fact(n-1);
}

処理の流れ

fact(4) を呼び出した場合、内部では次のように計算が展開されていきます。

fact(4)
= 4 * fact(3)
= 4 * 3 * fact(2)
= 4 * 3 * 2 * fact(1)
= 4 * 3 * 2 * 1
= 24

注意点

再帰による実装はコードがシンプルで直感的ですが、引数が大きくなると呼び出しが深くなり、スタックオーバーフローを引き起こす可能性があります。実用的な用途では、引数の範囲に注意するか、繰り返し処理による実装を検討するとよいでしょう。