再帰による階乗
CoddyのC++ジャーニー「論理と制御フロー」セクションの一部 — レッスン 46/56。
ある数の階乗は、再帰の動作を実演するための完璧な例です。nの階乗（n!と表記）は、1からnまでのすべての正の整数の積です。例えば、5! = 5 × 4 × 3 × 2 × 1 = 120 です。
階乗が再帰に理想的である理由は、それが自分自身を用いて定義できるからです：n! = n × (n-1)!。つまり、5! を計算するには 5 に 4! を掛け、4! を計算するには 4 に 3! を掛ける、というように続いていきます。
再帰的な階乗関数は次のようになります：
int factorial(int n) {
if (n <= 1) { // ベースケース：0! と 1! はどちらも 1 に等しい
return 1;
}
return n * factorial(n - 1); // 再帰ステップ：n! = n × (n-1)!
}基底ケースは、nが1または0に達したときに再帰を停止し、1を返します。再帰ステップでは、現在の数値に、1つ小さい数値の階乗を掛け合わせます。factorial(4)を呼び出すと、基底ケースに達するまで連続して呼び出しを行うことで 4 × 3 × 2 × 1 を計算し、呼び出しが戻る際にすべての結果を掛け合わせます。
チャレンジ
簡単再帰的な階乗関数を実装し、それを使用してさまざまな入力値の階乗を計算するプログラムを作成してください。このチャレンジでは、ベースケースに達するまで変更されたパラメータで関数自体を呼び出すことにより、再帰がどのように機能するかについての理解をテストします。
以下の入力が提供されます：
- 階乗を計算する数値を表す整数
n
プログラムは以下の手順で行う必要があります：
- 整数パラメータを受け取り、整数を返す
factorialという名前の再帰関数を作成します - 関数はベースケースを実装する必要があります：もし
nが1以下の場合は、1を返します - 関数は再帰ステップを実装する必要があります：
nにn-1の階乗を掛けた値を返します - メイン関数で、入力値を読み取ります
- 入力値を使用して階乗関数を呼び出します
- 指定された形式を使用して結果を出力します
以下の正確な出力形式を使用してください：
Factorial of [n] is [result]階乗関数は、再帰呼び出しのたびにベースケースに近づくよう、毎回より小さい値で自身を呼び出す必要があることに注意してください。ベースケースは、n が1または0に達したときに停止することで、無限再帰を防ぎます。再帰ステップでは、現在の数値に次に小さい数値の階乗を掛け合わせ、関数呼び出しが値を返すにつれて最終的な結果を構築していきます。
チートシート
nの階乗（n!）は、1からnまでのすべての正の整数の積です。これは再帰的に次のように定義できます：n! = n × (n-1)!
再帰的な階乗関数：
int factorial(int n) {
if (n <= 1) { // ベースケース：0!と1!はどちらも1に等しい
return 1;
}
return n * factorial(n - 1); // 再帰ステップ：n! = n × (n-1)!
}ベースケースは、nが1または0に達したときに再帰を停止します。再帰ステップでは、現在の数に1つ小さい数の階乗を掛けます。
自分で試してみよう
#include <iostream>
using namespace std;
// TODO: ここに階乗関数を記述してください
int main() {
// 入力を読み込む
int n;
cin >> n;
// TODO: 階乗関数を呼び出し、結果を保存します
// 結果を出力する
cout << "Factorial of " << n << " is " << result << endl;
return 0;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
