概要（再帰は「自分自身を呼び出して問題を小さく解く」ための仕組み）
再帰は、関数の中でその関数自身を呼び出すテクニックです。ポイントは、問題を「少し小さい同じ形」に分解し、最終的に簡単に答えられる“基底ケース”に到達させること。再帰は木構造の処理や分割統治で威力を発揮しますが、設計を誤ると無限再帰や性能低下の原因になります。正しく使うために「基底ケース（終了条件）」「再帰ステップ（縮小）」「コールスタック（呼び出しの積み重ね）」を押さえましょう。
# 最小の再帰イメージ：カウントダウン
def countdown(n):
if n <= 0: # 基底ケース（終了条件）
print("終了")
return
print(n)
countdown(n - 1) # 再帰ステップ（少し小さく）
基本構造と考え方（ここが重要）
基底ケース（終了条件）を必ず用意する
“いつ終わるか”を先に決めます。基底ケースがないと呼び出しが止まらず、スタックオーバーフロー（RecursionError）になります。数の問題なら「0や1に達したら終了」、構造の問題なら「空・葉に達したら終了」が定番です。
def factorial(n):
if n == 0: # 0! = 1 が基底ケース
return 1
return n * factorial(n - 1)
再帰ステップ（問題を“必ず”小さくする）
毎回、元の問題より小さい同型の問題へ進めます。n→n-1、リスト→先頭を除いた残り、木→子ノードへ、など縮小が必須です。縮まない再帰は止まりません。
def sum_list(xs):
if not xs:
return 0
return xs[0] + sum_list(xs[1:]) # 要素を1つ減らす
コールスタック（呼び出しの積み重ね）と実行の流れ
関数が呼ばれるたびに“スタック”に積まれ、基底ケースに到達したあと「積まれた順に戻り値が返る」ことで答えが組み上がります。深さがそのまま呼び出しコストになるため、深い再帰は負荷が高くなります。
よくある例題（定番から最短ルートで理解する）
階乗（n!）
def factorial(n: int) -> int:
if n < 0:
raise ValueError("負の階乗は定義外")
if n == 0:
return 1
return n * factorial(n - 1)
フィボナッチ（メモ化ありとなしの違い）
単純再帰は重複計算が爆発します。メモ化で大幅に高速化できます。
# 単純再帰（遅い）
def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# メモ化（速い）
def fib_fast(n: int, memo: dict[int, int] | None = None) -> int:
memo = memo or {}
if n in memo:
return memo[n]
if n <= 1:
memo[n] = n
else:
memo[n] = fib_fast(n - 1, memo) + fib_fast(n - 2, memo)
return memo[n]
最大公約数（ユークリッドの互除法）
「大きい問題を自然に縮める」再帰の良例。
def gcd(a: int, b: int) -> int:
return a if b == 0 else gcd(b, a % b)
二分探索（ソート済み配列）
区間を半分に縮めながら探索します。
def binary_search(xs, target, left=0, right=None):
right = len(xs) - 1 if right is None else right
if left > right:
return -1
mid = (left + right) // 2
if xs[mid] == target:
return mid
if xs[mid] < target:
return binary_search(xs, target, mid + 1, right)
else:
return binary_search(xs, target, left, mid - 1)
実務的な使いどころ（木構造・ファイル探索・JSON処理）
木構造の走査（深さ優先探索）
親→子へ“同じ処理を繰り返す”のが再帰と相性抜群です。
def dfs(node):
visit(node)
for child in node.children:
dfs(child)
ディレクトリの再帰探索（簡易版）
import os
def walk(path):
for name in os.listdir(path):
p = os.path.join(path, name)
if os.path.isdir(p):
walk(p) # ディレクトリなら潜る
else:
handle_file(p) # ファイルなら処理
ネストしたJSONの検索・集計
辞書とリストが入れ子になったデータから特定キーを抽出する処理は、再帰で素直に書けます。
def find_key(data, key):
if isinstance(data, dict):
if key in data:
yield data[key]
for v in data.values():
yield from find_key(v, key)
elif isinstance(data, list):
for item in data:
yield from find_key(item, key)
重要ポイントの深掘り（安全性・性能・設計の線引き）
再帰の深さと限界（RecursionError）
Python の再帰深さには上限があります（標準では約1000前後）。深い構造や大きい入力ではループや明示的スタック（リスト）への置き換えを検討しましょう。
import sys
# sys.getrecursionlimit() で上限確認、sys.setrecursionlimit(n) で変更可能（推奨は慎重に）
尾再帰最適化は「ない」前提で設計する
一部言語にある“尾再帰最適化”は Python にはありません。同じ処理ならループの方が高速・安全なことが多いです。再帰は「表現が自然で短くなる」場面に絞るのがプロの判断。
メモ化と分割統治で“再帰の旨み”を活かす
重複計算が多いときはメモ化（キャッシュ）で劇的に速くなります。マージソート・クイックソート・木の計算など、問題を半分や部分に分ける分割統治は再帰と相性が良いです。
def memoize(fn):
cache = {}
def wrapper(x):
if x in cache:
return cache[x]
cache[x] = fn(x)
return cache[x]
return wrapper
デバッグは「インデント付きログ」でトレース
どの深さで何が起きているかを可視化すると、再帰の理解が急速に進みます。
def trace_factorial(n, depth=0):
print(" " * depth + f"factorial({n})")
if n == 0:
return 1
res = n * trace_factorial(n - 1, depth + 1)
print(" " * depth + f"-> {res}")
return res
まとめ
- 再帰は「基底ケース」「再帰ステップ」「コールスタック」を押さえるのが土台。毎回“必ず小さくする”設計が生命線です。
- 定番の例（階乗・フィボナッチ・GCD・二分探索）で感覚を掴み、木構造・ディレクトリ・ネストJSONなど“入れ子構造”に適用すると効果的。
- Python は尾再帰最適化がないため、深い再帰はループや明示スタックへ切り替える判断を持つ。メモ化・分割統治で再帰の強みを最大化。
- トレース出力で実行の流れを見える化し、RecursionError を避けるために深さ・上限にも意識を向ける。
この線引きを体に入れると、再帰は「難しい魔法」ではなく、「見通しの良い分解の技」になります。まずは自分の問題を“同じ形の小問題”に分けられるか、紙に書いて整理するところから始めましょう。