C++ で数値の階乗を計算する

C++では、非負整数について、2からnまでの値を掛け合わせてn!を計算します。通常は反復ループが最も簡単で、再帰を使うと数学上の定義により直接沿った形になります。以下の例では両方の方法を示し、unsigned long longで扱える値の限界も説明します。

階乗の定義と入力値

非負整数nの階乗n!は、1からnまでの正の整数をすべて掛け合わせた積です。定義により0!は1です。これは、掛ける値がない場合でも階乗を含む式が一貫して扱えるようにするためです。たとえば、5!は5 * 4 * 3 * 2 * 1を意味します。

以下の例は、非負整数を入力として階乗を計算します。階乗は順列、組み合わせ、確率の計算で使われます。値は急速に大きくなるため、入力が有効でも、結果が特定のC++整数型で表現できるとは限りません。

反復で階乗を計算する

反復法では積を保持し、2からnまでの各整数を順に掛けます。積を1から始めると0と1のどちらも正しく扱えます。この場合、ループは実行されず、初期値がそのまま正しい結果になります。

次の例を実行します。

このセクションのコードと表示されるラベルや出力は英語のままです。

#include <iostream>

unsigned long long factorial(unsigned int n) {
  unsigned long long result = 1;
  for (unsigned int factor = 2; factor <= n; ++factor) {
    result *= factor;
    if (factor == n) {
      break;
    }
  }
  return result;
}

int main() {
  std::cout << "5! = " << factorial(5) << '\n';
}

5! = 120

累積値のresultには、それまでに計算した積が入ります。ループを1回実行するごとに、次の因子を掛けます。factorがnに達すると、breakでループを抜けます。これにより、符号なしカウンターが最大値に達したとき、ループ更新で値が折り返すのを防ぎます。nが0または1ならループは実行されず、初期値の1が結果として残ります。この方法で使うコールスタックの容量は一定です。

再帰で階乗を計算する

再帰では、等式n! = n * (n - 1)!に沿って計算します。基底ケースでは、nが0または1なら1を返します。それ以外の呼び出しでは、より小さな値を使うため、最終的に基底ケースに到達します。

このセクションのコードと表示されるラベルや出力は英語のままです。

#include <iostream>

unsigned long long factorial(unsigned int n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

int main() {
  std::cout << "5! = " << factorial(5) << '\n';
}

5! = 120

この関数は数学上の定義と結び付けて理解しやすい一方、基底ケースに達するまで段階ごとに関数呼び出しが発生します。再帰が深くなると、コールスタックの使用量も増えます。また、引数が符号なし型なので、負の値は受け付けません。符号付きの入力を受け取る場合は、符号なし型に変換する前に確認してください。この例の実行結果は5! = 120です。

入力の制限と整数オーバーフローへの対処

ここでは階乗を非負整数について定義します。unsigned intを受け取る関数に渡す前に、符号付きの入力を確認してください。負の値を符号なし型に変換すると、大きな正の値に変わります。

両方の例ではunsigned long longを使います。C++の規格上、この型は少なくとも20!までを表現できますが、すべての階乗を表せるわけではありません。乗算結果が型の最大値を超えると、符号なし整数の演算は最大値に1を加えた数を法として折り返します。その値は数学上の階乗とは異なります。より大きな入力を扱う場合は、多倍長整数ライブラリを使うか、乗算ごとにresult <= max / factorを確認してください。ここでmaxはstd::numeric_limits<unsigned long long>::max()です。

方法を選ぶ

単純な計算でコールスタックの使用量を一定に保ちたい場合は、反復法を使います。階乗の定義に直接沿う形のほうが周囲のアルゴリズムを理解しやすい場合は、利用できるスタックに収まる小さな入力に限って再帰を使います。どちらの方法でも、アプリケーションが必要とする最大の結果を表現できる数値型を選び、入力とオーバーフローの制限を明示的に扱ってください。階乗は組み合わせや確率の例で役立ちますが、組み込み整数型の範囲を超える値を扱う実用的なプログラムでは、式の代数的な簡約や多倍長整数型が有効な場合があります。