女性向けエンジニアスクール
3秒でわかる
関数が自分自身を呼び出して問題を小さく分けていく書き方。階層の深さが決まっていない木構造やフォルダの探索を短く表すために使います。
もう少し詳しく
どういうものか
再帰は、関数の中でその関数自身を呼び出す書き方です。同じ形をした一回り小さい問題に置き換えていき、これ以上分けられないところ（基底条件）で答えを返して戻ってきます。必ず必要な部品は二つで、分割していく再帰呼び出しと、止まるための基底条件です。どちらかが欠けると、止まらないか、そもそも答えが出ません。
なぜ必要か
繰り返しの回数が事前に分からない形、とくに階層構造の走査で強みが出ます。フォルダの中にフォルダがあり、その中にもフォルダがある、という構造は、何重になるかを書き手が決められません。ループで書くと自分でスタックを用意して積み下ろしする処理が必要ですが、再帰なら「中身がフォルダならもう一度自分を呼ぶ」の一行で表せます。木構造の探索、JSON の入れ子の走査、クイックソートやマージソートの分割も同じ形です。
具体例
import os
def find_py_files(path):
found = []
for name in os.listdir(path):
full = os.path.join(path, name)
if os.path.isdir(full):
found += find_py_files(full) # 自分を呼ぶ
elif name.endswith(".py"):
found.append(full)
return found
# 階乗は基底条件が分かりやすい例
def fact(n):
if n <= 1: # 基底条件
return 1
return n * fact(n - 1)つまずきやすいところ
止まらない再帰はスタックオーバーフローになります。Python では既定の再帰上限がおよそ 1000 回で、それを超えると RecursionError が出ます。上限を引き上げる前に、基底条件が本当に到達するかを確かめる方が確実です。引数が小さくなっていない、あるいは引数を減らす処理が条件分岐の中に隠れていて通らない、というのがよくある原因です。
もう一つは、素朴なフィボナッチのように同じ計算を何度も繰り返す形です。fib(n-1) と fib(n-2) の中で同じ値が重複して計算され、n が 40 を超える頃には現実的な時間で終わらなくなります。計算済みの答えを辞書に覚えておく（メモ化）か、下から積み上げるループに書き換えると解決します。
覚え方
合わせ鏡ではなく、ロシアの入れ子人形を思い浮かべると腑に落ちます。開けるたびに一回り小さくなり、開かない最後の一体が基底条件です。
