再帰関数は自分自身を呼び出す関数です。階層構造やツリー構造の処理に適していますが、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 の再帰制限
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 で再帰を使う際は、深さが限定的なケース（ツリー探索など）に留め、深い再帰にはループを使いましょう。
