階乗（再帰）
再帰は「関数が自分自身を呼ぶ」書き方です。ループと並ぶ繰り返しの道具ですが、書き方を一つ間違えると永遠に終わらないプログラムになります。まずはその失敗から見ていきます。
呼んだきり、戻ってこない
次の関数は、渡された数を表示してから、1 小さい数で自分自身を呼びます。
Python
def countdown(n):
print(n)
countdown(n - 1)countdown(3) を動かすと、3, 2, 1, 0, -1, -2 と表示が止まりません。しばらくすると RecursionError (Java なら StackOverflowError) が出て落ちます。
落ちるのは、呼び出しが終わっていないからです。countdown(3) は countdown(2) を呼び、その答えを待っている状態のまま残ります。
プレーンテキスト
countdown(3) が countdown(2) を待つ
countdown(2) が countdown(1) を待つ
countdown(1) が countdown(0) を待つ
countdown(0) が countdown(-1) を待つ ...待っている関数は「終わったらどこへ戻るか」の記録を残したまま積み上がり、その置き場がいつか満杯になります。止まらない理由は単純で、この関数には「ここで終わり」と書いた場所が一つも無いからです。
終わる条件を先頭に置く
再帰関数は必ず 2 つの部分でできています。これ以上分解しなくてよい最小のケースで、自分を呼ばずに終わる部分。そして自分自身を呼ぶ部分です。前者を基底ケース、後者を再帰ケースと呼びます。
Python
def countdown(n):
if n == 0:
print("発射")
return
print(n)
countdown(n - 1)追加した 3 行が基底ケースです。これがあると countdown(3) は 3, 2, 1, 発射 と表示して止まります。基底ケースを関数の先頭に置くと「まず止まるかどうかを確かめ、そうでなければ進む」という形になり、読む側にも意図が伝わります。
基底ケースに近づいているか
基底ケースを書いても、まだ止まらないことがあります。呼び出すたびに引数が基底ケースへ近づいていない場合です。
Python
def countdown(n):
if n == 0:
return
countdown(n) # n が変わらないので、永遠に終わらないn をそのまま渡し直しているだけなので、何段降りても状況が変わりません。次のように、縮めているつもりで逆向きに動かしているのも同じことです。
Python
def countdown(n):
if n == 0:
return
countdown(n + 1) # 0 から遠ざかっていく再帰を 1 本書いたら、次の 2 つを声に出して確かめてください。止まる条件を書いたか。そして、その条件へ向かって引数が毎回小さくなっているか。この 2 つが揃っていれば、再帰は必ず終わります。
逆に言うと、再帰が止まらないときに疑う場所もこの 2 つだけです。エラーの中身を読み込む前に、まず基底ケースの有無と、引数の動く向きを見てください。
詰まったら、紙に
countdown(3)の呼び出しを 1 段ずつ縦に書き下してみてください。どこまで降りて、どこから戻ってくるのかが目で見えるようになります。
要件
- 関数
factorial(n)を実装し、整数値を返す - for / while を使わず、必ず再帰呼び出しで実装する
- 基底ケース (n <= 1) を最初に書き、それ以外は n * factorial(n - 1) を返す
入出力例
factorial(0) → 1
factorial(1) → 1
factorial(5) → 120
factorial(6) → 720
factorial(10) → 3628800ヒント
