Factorial
整数 n の階乗は n! と表記し、1 から n までのすべての整数の積です。たとえば、4! = 1 × 2 × 3 × 4 = 24 です。定義により、0! = 1 です。関数は n を受け取り、n! を返します。
関数
- ninteger
- 階乗を計算する対象の整数
- 戻り値integer
- 1からnまでのすべての整数の積。nが0の場合は1です
制約
0 ≤ n ≤ 12- 答えは符号付き32ビット整数に収まります。最大の値は
12! = 479001600です。
例
- 入力
- n = 5
- 出力
- 120
- 説明
1 × 2 × 3 × 4 × 5を掛けます。途中の積は1、2、6、24となり、最後は120になります。
- 入力
- n = 0
- 出力
- 1
- 説明
- 掛けるものは何もなく、因数がない積は
1です。これが0! = 1である理由です。
発展問題
100!は158桁です。計算せずに、末尾にゼロがいくつ並ぶか数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
4!と5!を積の形で書き出してください。5!は4!とどのような関係がありますか？5! = 5 × 4!。一般に、n! = n × (n-1)!であり、0! = 1で連鎖は止まります。1から始まる積を保持し、2からnまでのすべての数を掛けていきます。1から始めることで、0と1の場合も正しい答えになります。
解説
階乗には2つの等価な記述があり、それぞれコードにできます。積としては、n! = 1 × 2 × ... × nで、これはループです。再帰的な定義としては、0! = 1およびn! = n × (n-1)!で、これは自分自身を呼び出す関数です。どちらもおよそn回の乗算を行います。最後に使うのはループのほうです。呼び出しスタックが不要だからです。
定義からの再帰
考え方
階乗は、より小さい階乗を使って定義されます。n! = n × (n-1)! です。4! = 24 をすでに知っていれば、5! = 5 × 24 = 120 となります。再帰関数は、この説明をコードとして記述します。factorial(n) を求めるために、factorial(n-1) を呼び出し、その答えに n を掛けます。
呼び出しを止める場所、つまり基底ケースが必要です。factorial(0) は何も呼び出さずに 1 を返します。呼び出しのたびに n が1ずつ減るため、5 から始めると、呼び出しは 5、4、3、2、1、0 と進みます。次に、答えが連鎖をさかのぼって返されます。1、1、2、6、24、120 です。
呼び出しは n + 1 回、乗算は n 回行われるため、時間計算量は O(n) です。それぞれの呼び出しは、その下の呼び出しが戻るまでスタック上で待機するため、スタックには n + 1 個のフレームが保持されます。これは空間計算量で O(n) です。n ≤ 12 ならごくわずかですが、同じパターンを大きな入力に適用するとスタックがオーバーフローします。
アルゴリズム
nが0の場合は、1を返します。これが基本ケースです。- そうでない場合は、
n-1に対して関数を呼び出します。 - その結果に
nを掛けて返します。
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)ループ内で掛け算する
考え方
再帰を展開すると、積を順次計算する処理になります。result = 1から始め、2を掛け、次に3を掛けるというように、nまで続けます。n = 5の場合、結果は1、2、6、24、120と推移します。
1から始めることで、最小の入力にも対応できます。n = 0およびn = 1の場合、2からnまでのループは一度も実行されず、関数は初期値の1を返します。これはどちらの場合にも正しい答えです。
このループではn-1回の乗算を行うため、時間計算量はO(n)で、数値を1つ保持するため、空間計算量はO(1)です。オーバーフローする呼び出しスタックがないため、再帰版を示した後は、面接官はこのバージョンを期待します。
アルゴリズム
result = 1を設定します。kを2からnまで（両端を含む）ループします。- 各ステップで
resultにkを掛けます。 resultを返します。
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
落とし穴と境界ケース
階乗のコードは短いため、バグは境界部分に潜んでいます。
- 積の初期値を
0にする。どのように掛け算しても、結果は常に0のままです。積の初期値は1です。 - 再帰を
n == 1のときだけ終了する。0で呼び出すと、その関数はベースケースに決して到達せず、スタックオーバーフローが発生するまで-1、-2と進み続けます。n == 0をベースケースにしてください。 k ≤ nではなくk < nでループする。最後の因数が抜け落ち、(n-1)!を返すため、5では120ではなく24になります。- オーバーフローを無視する。
13! = 6227020800は符号付き32ビット整数に収まりません。JavaとC#では積が警告なしに誤った数値へ折り返し、Cでは符号付き整数のオーバーフローは未定義動作となり、Rustのデバッグビルドではパニックが発生します。64ビット整数で保持できるのは20!までで、それより大きな値には多倍長整数が必要です。 - Swiftで
for k in 2...nと書く。終点が始点より小さい閉区間は、nが0または1のとき、実行時にクラッシュします。
よくある質問3
階乗を計算する時間計算量はどれくらいですか？
ループと再帰はどちらも、n までの各数について1回ずつ乗算を行うため、時間計算量は O(n) です。ループが必要とする追加領域は O(1) です。再帰では、基底ケースから戻るまで呼び出しごとにスタックフレームが1つ保持されるため、O(n) の領域を使用します。
なぜ 0! は 1 に等しいのでしょうか？
0!は数を一つも掛け合わせない積であり、因数のない積は1です。これは、項のない和が0であるのと同じです。また、n = 1のときも規則n! = n × (n-1)!が成り立ちます。1! = 1 × 0! = 1です。数え上げの結果も一致します。項目が0個の場合、並べ方はちょうど1通りです。
階乗には再帰とループのどちらが適していますか？
どちらも同じ乗算を行い、同じ答えを返します。再帰版は数学的な定義のように読めるため、再帰の古典的な初歩の練習問題となっています。ループはメモリ使用量が一定で、コールスタックがオーバーフローすることもないため、実際のコードではこちらのほうが適しています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def factorial(n):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
n = 5
期待される出力
120