Python の再帰関数と末尾再帰最適化の限界

再帰関数は自分自身を呼び出す関数です。階層構造やツリー構造の処理に適していますが、Python には末尾再帰最適化がないため、深い再帰には注意が必要です。

基本的な再帰

階乗を計算する例です。

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

再帰には「基底条件」（終了条件）が必須です。なければ無限ループになります。

末尾再帰は、再帰呼び出しが関数の最後の処理になっている形式です。

def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)

一部の言語では、末尾再帰をループに変換する「末尾再帰最適化」が行われます。しかし Python はこの最適化を行いません。

Python にはデフォルトで再帰の深さ制限があります。

import sys
print(sys.getrecursionlimit())  # 通常 1000

深い再帰は RecursionError を引き起こします。

factorial(1500)  # RecursionError

深い再帰が必要な場合は、ループに書き換えるのが一般的です。

def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

再帰制限を変更することも可能ですが、スタックオーバーフローの危険があるため推奨されません。

sys.setrecursionlimit(3000)  # 非推奨

Python で再帰を使う際は、深さが限定的なケース（ツリー探索など）に留め、深い再帰にはループを使いましょう。