関数が、自分自身を呼ぶ。初めて再帰を見たとき、多くの人が戸惑います。自分を呼んだら、また自分を呼んで、永遠に終わらないのではないか、と。
でも、正しく書かれた再帰は、ちゃんと終わって、ちゃんと答えを返します。なぜでしょうか。
再帰が難しく感じるのは、才能の問題ではありません。 「関数を呼ぶと裏で何が積まれるのか」 を知らないだけです。
▶ アニメーションで見たい方はこちら（約13分）
https://youtu.be/9Z1vOWaIjuE
この記事では、コールスタックという舞台装置を底から見て、再帰がなぜ動くのかを組み立てます。
コールスタック — 呼び出しは積まれる
再帰の前に、まず「関数を呼ぶ」とは何かを正確に見ます。
プログラムにはコールスタックという領域があります。関数を呼ぶたびに、その関数のための箱がスタックに積まれます。この箱をスタックフレームと呼びます。
フレームの中には、その関数の引数、ローカル変数、そしてどこに戻るかという戻り先が入っています。
関数Aが関数Bを呼ぶと、Bのフレームが Aの上に積まれます。Bが終わると、Bのフレームは下ろされ、Aの続きに戻ります。お皿を積んで、上から取っていくのと同じです。後に積んだものから先に下ろす。これがスタックです。
再帰とは、この積み下ろしが、同じ関数同士で起きるだけのことです。仕組みは、まったく特別ではありません。
再帰の2つの部品 — 基底ケースと再帰ケース
正しい再帰には、必ず2つの部品があります。
1つ目、基底ケース。これ以上分解しない、答えが直接わかる一番小さい場合です。再帰を止めるブレーキです。
2つ目、再帰ケース。問題を一回り小さくして、自分自身に委ねる部分です。
例えば階乗。nの階乗は、n × n-1の階乗です。基底ケースは「0の階乗は1」。これだけです。
def factorial(n):
if n == 0: # 基底ケース: これ以上分解しない
return 1
return n * factorial(n - 1) # 再帰ケース: 一回り小さい問題に委ねる
大事なのは、再帰ケースが呼ぶたびに、問題が基底ケースに必ず近づくことです。nがn-1になり、いつか0にたどり着きます。近づかなければ、ブレーキの無い車と同じで、永遠に止まりません。
「止まる場所」と「小さくして委ねる」。この2つが揃って初めて、再帰は答えを返します。
階乗で見る — 積み上げと畳み込み
factorial(3) を、コールスタックで完全に追いかけてみましょう。
factorial(3) は、3 × factorial(2) を計算したい。でも factorial(2) の答えがまだ無いので、計算を中断して、factorial(2) を呼びます。フレームが積まれます。
factorial(2) も、2 × factorial(1) で中断。factorial(1) も、1 × factorial(0) で中断。フレームがどんどん積み上がります。これが下りの旅です。
factorial(3)
└─ factorial(2)
└─ factorial(1)
└─ factorial(0) ← 基底ケース。答えは 1 と直接わかる
そして factorial(0)。これは基底ケースです。答えは1と、直接わかります。ここで折り返します。
1を返すと、factorial(1) が再開して 1×1 で 1。それを返すと factorial(2) が 2×1 で 2。さらに factorial(3) が 3×2 で 6。フレームが次々下ろされ、答えが下から上へ運ばれます。これが上りの旅です。
積んで、折り返して、畳み込む。再帰は、この往復です。
基底ケースを忘れると — スタックオーバーフロー
では、基底ケースを忘れたらどうなるでしょうか。
def bad_factorial(n):
return n * bad_factorial(n - 1) # 止まる条件がない！
factorial(n) が、止まる条件なしに factorial(n-1)、factorial(n-2)、と呼び続けます。問題は小さくなっても、0で止まらず、マイナスへ進んでいきます。フレームは積まれ続けます。
しかし、コールスタックの大きさには限界があります。Pythonは既定で約1,000フレーム（sys.getrecursionlimit()で確認・変更できます）、JavaScriptの主要エンジンでも数千から数万フレームほどです。そこを超えた瞬間、スタックオーバーフロー。プログラムは強制終了します。
Pythonでは RecursionError、JavaScriptでは RangeError: Maximum call stack size exceeded として現れます。あの有名な質問投稿サイトの名前の由来も、ここにあります。
再帰のバグの大半は、ここにあります。基底ケースを書き忘れた。あるいは、再帰ケースが基底に近づいていない。 「このまま呼び続けて、本当に止まるか?」 を、書くたびに自問する。それが再帰の鉄則です。
なぜスタックなのか — 「中断して戻る」の管理
ここで一つ疑問が湧きます。なぜ、関数の呼び出しは「スタック」で管理されるのでしょうか。キューでも、リストでもなく。
理由は、関数の呼び出しが必ず入れ子になるからです。Aが Bを呼び、Bの中で Cを呼ぶ。このとき、必ず Cが一番先に終わり、次に B、最後に Aの順で終わります。後から始めたものが、先に終わる。
これは、まさにスタックの性質、LIFO（Last In, First Out）そのものです。最後に中断した処理を、最初に再開する。だからスタックがぴったり合います。
そして再帰では、同じ関数のフレームがこの順序で積まれ、基底ケースから順に、最後に積んだものから畳み込まれていきます。スタックという仕組みが、再帰の「往復」をそのまま支えているのです。
再帰 vs ループ — 同じ計算の2つの表現
再帰でできることは、多くの場合、ループでも書けます。両者は、同じ計算の違う表現です。
# 再帰版: 状態はコールスタックのフレームたちに分散される
def factorial_recursive(n):
if n == 0:
return 1
return n * factorial_recursive(n - 1)
# ループ版: 状態は変数 1 つに集約される
def factorial_loop(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
階乗をループで書くと、結果を入れる変数を1つ用意し、1からnまで掛けていきます。状態は変数1つに保持されます。
再帰版では、その「途中までの計算状態」が、コールスタックのフレームたちに分散して保持されています。ループが明示的に持つ状態を、再帰は暗黙にスタックへ預けているのです。
ならばどちらを使うべきでしょうか。単純な繰り返しはループが素直で、スタックも消費しません。一方、木のように枝分かれする構造や分割統治では、再帰のほうが圧倒的に自然に書けます。道具の使い分けです。
木構造と再帰 — 自己相似に効く
再帰が最も輝くのは、自己相似な構造です。全体と部分が、同じ形をしているものです。
一番身近な例が、フォルダです。フォルダの中には、ファイルと、さらにフォルダが入っています。その中のフォルダにも、また中身があります。
このフォルダの中身を全部数える処理を考えてみます。「ファイルなら1と数える。フォルダなら、その中身を同じやり方で数える」。これだけで、どんなに深い階層でも、すべて数えられます。
import os
def count_files(path):
if os.path.isfile(path):
return 1 # 基底ケース: ファイルなら 1
total = 0
for entry in os.listdir(path):
total += count_files(os.path.join(path, entry)) # フォルダなら再帰
return total
部分が全体と同じ形をしているなら、全体に対する処理を、そのまま部分に適用できます。これが再帰の真骨頂です。同じ構造は、WebページのHTML（DOMツリー）、組織図、数式の構文木にもあります。木を扱うコードは、ほぼ必ず再帰で書かれます。
分割統治 — 半分に分けて解く
再帰のもう一つの大舞台が、分割統治です。大きな問題を、小さく分けて解き、結果を統合する戦略です。
例えば、バラバラの数列を並べ替えるマージソート。まず列を半分に分けます。その半分を、また半分に分ける。一つになるまで分け続けます。一つなら、もう並んでいます。これが基底ケースです。
そして上りの旅で、並んだ列同士を、順序を保ったまま統合していきます。半分と半分を合体させると、全体が並びます。
注目すべきは、「半分を並べ替える」処理が、元の問題とまったく同じ形だということです。だから自分自身に委ねられます。分割統治は、クイックソート、巨大データの処理にも現れる、再帰の王道パターンです（詳しくは姉妹記事「ソートアルゴリズムはなぜ賢いと桁違いに速いのか」で扱っています）。
再帰の落とし穴 — フィボナッチの指数爆発
再帰には、強力さゆえの落とし穴もあります。フィボナッチ数列で見てみましょう。
フィボナッチは、fib(n) が fib(n-1) + fib(n-2)。素直に再帰で書けます。
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
しかし、その呼び出しの木を描くとぞっとします。fib(5) を計算するのに fib(3) が2回、fib(2) が3回と、同じ計算が何度も繰り返されます。nが大きくなると、呼び出し回数はほぼ2のn乗。指数爆発です。fib(50) で、もう天文学的な回数になります。
原因は、同じ部分問題を、毎回ゼロから解き直していることです。
解決はシンプルです。一度計算した答えを記録しておき、次は記録から返す。これをメモ化と呼びます。
from functools import lru_cache
@lru_cache(maxsize=None) # 計算済みの (n, 結果) を記録し、2 回目以降は即返す
def fib_memo(n):
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
print(fib_memo(50)) # 素朴な再帰では実質終わらないが、メモ化なら一瞬
これだけで、指数時間が一気に直線的な時間まで落ちます。再帰は強力ですが、「同じ計算を重ねていないか」は常に疑うべきです。
末尾再帰最適化 — スタックを増やさない
スタックオーバーフローの不安を、別の角度から解く技術もあります。末尾再帰最適化です。
鍵は、再帰呼び出しが関数の一番最後の処理になっているかどうかです。これを末尾呼び出しと言います。
普通の再帰は、n * factorial(n-1) のように、呼び出しの後に掛け算が残っています。だから前のフレームを覚えておく必要があります。
# 普通の再帰: 呼び出しの後に掛け算が残る (末尾呼び出しではない)
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
# 末尾再帰: 計算途中の結果 (acc) を引数で持ち回り、
# 再帰呼び出しが最後の処理になっている
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, n * acc)
計算途中の結果を引数で持ち回り、再帰呼び出しが最後の処理になるよう書き換えると、前のフレームにはもう用がなくなります。このとき、処理系は古いフレームを捨てて使い回せます。スタックは増えず、実質ループと同じになります。これが末尾再帰最適化です。
ただし注意が必要です。この最適化をする言語と、しない言語があります。例えば多くの実行環境のJavaScriptやPython（CPython）は、これを行いません。上記の factorial_tail をPythonで巨大なnに対して呼んでも、素朴な再帰と同様にスタックオーバーフローします。過信は禁物です。
再帰的思考 — 小さい自分に委ねる
最後に、再帰を書くときの考え方です。
初心者がつまずくのは、スタックの積み下ろしを全部頭の中で追おうとすることです。深くなると、必ず迷子になります。
熟練者はそうしません。考えるのは、たった2つです。
一つ、基底ケース。一番小さい場合の答えは何か。
二つ、一段だけの再帰ケース。「もし、一回り小さい問題の答えが、すでに手に入っているとしたら、それを使って今の答えをどう作るか」。
その「一回り小さい問題」を解くのは、未来の自分に任せます。中身は追わず、ただ信じる。この 「小さい自分を信じる」 飛躍ができると、再帰は驚くほど書きやすくなります。全部を追うのではなく、一段を正しく書く。それが再帰的思考です。
まとめ
再帰の正体は、特別な魔法ではなく、コールスタックの往復でした。呼ぶたびにフレームが積まれ、基底ケースで折り返し、畳み込まれて答えが戻ります。
正しい再帰には、必ず2つの部品があります。止まるための基底ケース、そして問題を小さくして委ねる再帰ケース。近づかなければ、スタックオーバーフローになります。
再帰が輝くのは、フォルダや木のような自己相似な構造、そして分割統治です。一方で、フィボナッチのような重複には、メモ化を。
そして書くときのコツは、全部を追わず、 小さい自分を信じる ことです。自分を呼ぶ関数は、なぜ終わるのか。その答えは、基底ケースに向かって、スタックを一段ずつ畳んでいくから、でした。
チャンネル: https://www.youtube.com/@base-technology （根本解説シリーズ）