再帰の仕組みをPythonの例でわかりやすく解説

再帰が解決する問題

問題の中には、自分自身を使って定義されるものがあります。フォルダにはファイルと他のフォルダが含まれ、木のノードは子の木を持ち、n の階乗は n に n − 1 の階乗を掛けたものです。これを普通のループで書くと、未処理の作業を積む明示的なスタックが必要になることが多いのですが、再帰なら言語がそのスタックを代わりに管理してくれます。

再帰関数は2つの部分でできています。

• 基底ケース：直接答えを返せる最小の入力です。階乗では 0! = 1 です。
• 再帰ケース：問題を小さくし、小さい部分に対して関数を呼び出し、結果を組み合わせます。階乗では n! = n × (n − 1)! です。

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

コールスタックを一歩ずつ追う

各呼び出しはコールスタック上に自分専用のフレームを持ち、そこに n の独自のコピーを保持します。呼び出しは基底ケースまで深く進み、その後、結果が逆の順序で戻ってきます。

ここでのスタックの深さは n + 1 フレームなので、リストを作らなくても追加の空間は O(n) になります。

入れ子のデータに対する再帰

再帰が最も役立つのは、データの形そのものが再帰的な場合です。次の関数は、他のリストを含みうるリストの中の数値を、何段の深さでもすべて合計します。

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

同じパターンで、ディレクトリツリー、JSONドキュメント、HTMLのDOM、二分木をたどれます。現在のノードを処理してから、各子に再帰するだけです。

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

再帰関数の計算量

コストは（呼び出し回数）×（1回あたりの仕事量）で見積もります。空間は少なくとも最大のスタックの深さになります。

マージソートの T(n) = 2T(n/2) + O(n) のような分割統治法の漸化式は、O(n log n) に解けます。n − 1 に対して2回呼び出す関数は、指数的に増加します。

メモ化：同じ計算の繰り返しをやめる

素朴なフィボナッチ関数は、同じ値を何度も再計算します。fib(5) は fib(3) を2回、fib(2) を3回呼び出します。各結果を最初に計算したときにキャッシュすれば、指数時間が線形時間になります。Pythonの functools.lru_cache（Python 3.9以降は functools.cache）なら、デコレータ1つで実現できます。

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

メモ化再帰は、動的計画法のトップダウン形式です。ボトムアップ形式では、ループで表を埋めていきます。

再帰の制限とループへの書き換え

sys.setrecursionlimit() で上限を引き上げることもできますが、非常に深い再帰ではインタプリタがクラッシュすることがあります。100万ノードの連結リストや偏った木のように深くなりうる入力では、ループと明示的なスタックを使って関数を書き直してください。

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

よくある間違い

• 基底ケースがない、または到達できない。たとえば上のコードで factorial(-1) を呼ぶと 0 に到達せず、RecursionError で終わります。
• 入力が小さくならない再帰ケース。たとえば f(n) の中で f(n) を呼ぶ場合です。
• 再帰の結果を return し忘れる。return なしの factorial(n - 1) は None を返します。
• 呼び出しのたびにデータをコピーする。items[1:] はリストをコピーするため、長いリストのスライスに再帰すると時間が O(n²) かかります。代わりにインデックスを渡してください。
• 呼び出し間で状態を持ち回すために def f(x, seen=[]) のような変更可能なデフォルト引数を使う。同じリストが関数のすべての呼び出しで共有されてしまいます。

再帰を使うべき場面

データや問題が自然に再帰的な場合に再帰を使います。木、グラフ（深さ優先探索）、入れ子構造、式の構文解析、バックトラッキング（順列、N-クイーン、数独）、分割統治法（マージソート、クイックソート、二分探索）などです。単純な列を扱う問題や、Pythonで入力サイズに応じて深さが増えうる場合は、ループを使ってください。

面接では、基底ケース、再帰ケース、スタックを含めた時間・空間コスト、メモ化が有効な場面を説明できるかを問う再帰の問題がよく出ます。