再帰とコールスタック
再帰関数が自分を呼び出すとき、コールスタックが未完了の仕事を保存します。呼び出しごとにフレームを作り、最新のフレームを実行し、戻り値を下で待つ呼び出し元へ渡します。待機中のフレームもメモリを使うため、計算が難しくなる前に深さの上限へ達することがあります。
フレームを付箋に置き換えて考えます。最初の付箋の fact(4) は、先に fact(3) を必要とするため、新しい付箋を上に置きます。処理するのは一番上だけで、下の付箋は未完了の仕事を保って待ちます。画面では付箋一枚がフレーム一つに対応し、待機ラベルはそのフレームに仕事が残っていることを示します。
再帰にコールスタックが必要な理由
再帰関数には基底ケースと再帰ケースがあります。基底ケースは再帰せずに戻ります。再帰ケースは小さい入力で呼び出し、戻り値を使って残りの仕事を終えます。
階乗の基底ケースは n <= 1 で、1 を返します。それ以外では fact(n) が fact(n - 1) を呼び、戻り値を child に保存して n * child を返します。
fact(4) が fact(3) を呼んでも、元のフレームは n = 4 と未確定の child = ? を保ちます。fact(3) が 6 を返すと、その値が child に入り、fact(4) は 4 * 6 を計算できます。
制御は後入れ先出しです。最後に積んだ呼び出しから戻り、待機中の各フレームはスタック領域を使います。
ステップごとの解説
既定では fact(4) を計算します。
answer = fact(n)から始まり、n = 4、スタックは空です。fact(4)を呼び、局所状態n = 4のフレームを積みます。4 <= 1は偽なので、基底ケースからは戻れません。fact(4)はchild = fact(3)で止まり、childの値を待ちます。fact(3)を上に積んで実行し、fact(4)は下で待ちます。fact(3)は3 <= 1が偽なので、child = fact(2)で待ちます。fact(2)を積みます。2 <= 1は偽で、child = fact(1)で待ちます。fact(1)を積みます。1 <= 1は真なので、基底ケースが1を返します。- 戻り値を
fact(2)に渡し、child = 1にします。 fact(2)が2 * 1 = 2を返します。fact(3)はchild = 2を受け取り、3 * 2 = 6を返します。fact(4)はchild = 6を受け取り、4 * 6 = 24を返します。- 最上位の呼び出しが
answer = 24を設定し、スタックは再び空になります。
方向の変化を見てください。呼び出しはフレームを上へ積み、戻り値は下の呼び出し元へ渡ります。fact(2) が先に終わらなければ、fact(4) は終われません。
次にコードを missingBase に切り替えます。基底ケースを取り除くと、先頭のフレームは次のフレームを要求し続け、戻りに到達しません。
時間計算量と空間計算量
| 方式 | 時間計算量 | スタック領域 | 挙動 |
|---|---|---|---|
基底ケースがある fact(n) | O(n) | O(n) | n から 1 まで一つずつフレームを作り、順に戻る |
fact_without_base(n) | 自力では終了しない | 再帰上限まで増える | 各フレームが次を呼び、戻りに到達しない |
本レッスンの単位コストモデルでは、各フレームの仕事は条件確認、必要な再帰呼び出し、戻る際の乗算という定数回の処理です。n フレーム（n >= 1）なので、時間とスタック領域は O(n) です。大きい n には、ループへの書き換え、明示的なスタックの利用、影響を確認したうえでの再帰上限の変更を検討します。
基底ケースのない版は階乗を実装していません。停止規則がなく、ランタイムの再帰上限で止まるだけです。Python の既定の上限は約 1000 フレームで、六つではありません。画面では失敗を追えるよう、小さい上限を使っています。
境界ケース
n = 1は直ちに基底ケースに入り、一つ積んだフレームが1を返して取り除かれます。- 通常入力の上限
n = 6は、六つのフレームを画面に収めるためです。階乗の定義の上限ではありません。 - 基底ケースがなければ、負の値でも止まりません。
fact_without_base(-2)はfact_without_base(-3)を呼び、次は-4と続きます。 - 戻り値の行き先は一つです。呼び出し元の待機中の
child、または最上位の呼び出しに対応する大域のanswerに入ります。
よくある間違い
- プログラム全体をコピーすると思う。 同じ関数に新しいフレームを作り、局所変数を別々に持ちます。
- 呼び出し元が待つことを忘れる。
fact(3)が戻るまで、fact(4)は乗算を終えられません。 - 基底ケースを任意と考える。 停止条件がなければ、ランタイムが止めるまでスタックが増えます。
- 呼び出し順と戻り順を混同する。 呼び出しの引数は
4, 3, 2, 1、戻り値は1, 2, 6, 24の順です。 childを一つの共有変数として考える。fact(2).childとfact(4).childは別フレームの領域です。
このレッスンでの簡略化
フレームには関数名、引数、局所変数 child、戻り値だけを表示します。実際の Python フレームは、バイトコード位置、大域変数やクロージャーへの参照、例外状態、インタープリターの管理情報も持ちます。ここでは、呼び出しごとにフレームがあり、現在はスタックの先頭だけが実行中だという点を追います。