Python で「RecursionError: maximum recursion depth exceeded」が解決できない

要約

RecursionError: maximum recursion depth exceeded は、関数の再帰呼び出しの深さが Python の既定上限（既定およそ 1000）を超えると送出されます。
大半は終了条件のバグによる無限再帰なので、上限を上げる前にベースケースを疑うのが鉄則です。

よくある原因

1. ベースケースの誤り: 再帰を止める条件が一度も真にならず、関数が自分を呼び続ける。
2. 正当に深い再帰: 木やグラフの探索など、データが大きく既定上限を正当に超えるケース。
3. 想定外の自己呼び出し: __getattr__ や __repr__ の中でその属性を再参照し、無限ループになる。

解決策

1. まずベースケースを点検する

無限再帰は上限を上げても解決しません。
終了条件が必ず到達するか確認します。

def factorial(n):
    if n <= 1:        # ← このベースケースが正しいか
        return 1
    return n * factorial(n - 1)

引数が単調に終了条件へ近づいているかを必ず確認してください。

2. 必要なときだけ上限を引き上げる

正当に深い再帰なら上限を調整します。

import sys
sys.setrecursionlimit(10000)

sys.setrecursionlimit は公式ドキュメント記載の正式 API ですが、上げ過ぎるとインタプリタがクラッシュする可能性があるため必要最小限にとどめます。

3. 反復処理へ書き換える

最も安全なのは再帰をループ＋明示的スタックに変換することです。

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

深い探索はスタックを使った反復に置き換えると、データサイズに依存せず安定します。