C++で階乗を求めるプログラム｜再帰・非再帰の2つの実装方法を解説

非負整数 n の階乗とは、n 以下のすべての正の整数を掛け合わせた積のことです。

たとえば、5 の階乗は次のように計算されます。

5! = 5 × 4 × 3 × 2 × 1
5! = 120

整数の階乗は、再帰的なプログラムまたは非再帰的なプログラムのいずれかで求めることができます。ここでは、両方の実装例をサンプルコードとともに紹介します。

方法1：非再帰プログラム（forループ）で階乗を求める

最もシンプルな方法は、for ループを使って 1 から n まで順番に掛け合わせていく方法です。以下のプログラムでその実装を見てみましょう。

サンプルコード

#include <iostream>
using namespace std;
int main() {
    int n = 5, fact = 1, i;
    for(i = 1; i <= n; i++)
        fact = fact * i;
    cout << "Factorial of " << n << " is " << fact;
    return 0;
}

実行結果

Factorial of 5 is 120

コードの解説

上記のプログラムでは、for ループが 1 から n まで繰り返し実行されます。各反復ごとに変数 fact にカウンタ変数 i を掛けていくことで、最終的に 1 から n までのすべての整数の積が fact に格納されます。

該当する部分のコードは以下の通りです。

for(i = 1; i <= n; i++)
    fact = fact * i;

方法2：再帰プログラムで階乗を求める

次に、再帰（リカーシブ）関数を使った階乗の計算方法を示します。

サンプルコード

#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 = 5;
    cout << "Factorial of " << n << " is " << fact(n);
    return 0;
}

実行結果

Factorial of 5 is 120

コードの解説

上記のプログラムでは、fact() が再帰関数として定義されています。main() 関数から、階乗を求めたい数値を引数として fact() を呼び出します。

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

引数が 0 または 1 の場合は fact() は 1 を返します。それ以外の場合は、引数を n - 1 として自分自身を再帰的に呼び出します。これにより、「n! = n × (n−1)!」という階乗の性質をそのままコードに表現できます。

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

注意点：オーバーフローに気をつけよう

階乗の値は増加が非常に速いため、int 型では 13! 以上でオーバーフローしてしまいます。大きな数値の階乗を扱う場合は、long long 型や unsigned long long 型を使用するか、さらに大きな値が必要な場合は多倍長整数ライブラリを検討してください。

まとめ

• 非再帰（forループ）方式： 処理の流れが直感的で、スタックオーバーフローの心配がないため、初心者にもおすすめの方法です。
• 再帰方式： 階乗の数学的な定義をそのまま反映したエレガントな実装ですが、深い再帰呼び出しが発生するため注意が必要です。

用途に応じて適切な方法を選択しましょう。