【Python】再帰のエラーを防ぐ

使用言語：Python 3.11.2

結論

Python3における再帰関数の実行回数のデフォルト上限は1000である
1000回以上再帰するには sys.setrecursionlimit() する

import sys

# set:再帰回数上限値の指定／引数にはPythonインタープリタのスタックの深さを指定する
sys.setrecursionlimit(100000)
# get:再帰回数上限値の取得
sys.getrecursionlimit()

実験

再帰回数の上限が995～998回となる場合

test.py

import sys

# 再帰関数testRecursionを実行する回数を定義する関数
def setGoal(n):
    global goal;goal = n
    print("■%d回実行する"%(n))

# 変数goalの数だけ実行する再起関数
def testRecursion(n=1):
    print("Recursion Limit : %d\nFinished at %d\n" % (sys.getrecursionlimit(),n)) \
          if n == goal else testRecursion(n+1)

# 再帰関数testRecursionを実行する回数を示す変数
goal = 0

# 再帰関数を実行する
try:
    setGoal(995);testRecursion()
    setGoal(996);testRecursion()
    setGoal(997);testRecursion()
except RecursionError:
    import traceback
    traceback.print_exc();print()
sys.setrecursionlimit(10000);setGoal(998);testRecursion()

実行結果

■995回実行する
Recursion Limit : 1000
Finished at 995

■996回実行する
Recursion Limit : 1000
Finished at 996

■997回実行する
Traceback (most recent call last):
  File "test.py", line 98, in <module>
    setGoal(997);testRecursion()
                 ^^^^^^^^^^^^^^^
  File "test.py", line 89, in testRecursion
    if n == goal else testRecursion(n+1)
                      ^^^^^^^^^^^^^^^^^^
  File "test.py", line 89, in testRecursion
    if n == goal else testRecursion(n+1)
                      ^^^^^^^^^^^^^^^^^^
  File "test.py", line 89, in testRecursion
    if n == goal else testRecursion(n+1)
                      ^^^^^^^^^^^^^^^^^^
  [Previous line repeated 993 more times]
  File "test.py", line 88, in testRecursion
    print("Recursion Limit : %d\nFinished at %d\n" % (sys.getrecursionlimit(),n)) \
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded while calling a Python object
Recursion Limit : 1000
Finished at 997

■998回実行する
Recursion Limit : 10000
Finished at 998

• sys.getrecursionlimit()が1000に対し997回目でRecursionErrorが出現
  • RecursionErrorが1000回目よりも前に出た理由は sys.getrecursionlimit() で取得できる値が厳密には「Pythonインタープリタのスタックの深さの最大値」であるため
  • 参考
• sys.setrecursionlimit(10000);したあとはRecursionErrorがスローされない

補足1

再起回数上限にも天井が存在する
闇雲に大きい値を設定することはできない

公式ドキュメントには以下のように記載されている

Python インタプリタの、スタックの最大の深さを limit に設定します。この制限は Python プログラムが無限に再帰し、 C スタックがオーバーフローしてクラッシュすることを防止するために設けられています。

limit の最大値はプラットフォームによって異なります。深い再帰処理が必要な場合にはプラットフォームがサポートしている範囲内でより大きな値を指定することができますが、この値が大きすぎればクラッシュするので注意が必要です。

補足2

かつてはスタック領域の容量も別途設定する必要があった
Python3.10までは threading.stack_size() を使うことで対応 （参考）

import sys
import threading

# 再帰回数上限値のセット。引数にはPythonインタープリタのスタックの深さを指定する
sys.setrecursionlimit(67108864)
#　2^20のstackメモリを確保
threading.stack_size(1024*1024)

• Python3.11からはPythonで書いた関数の再帰ではスタックを消費しなくなった
  • フィボナッチや階乗について約1.7倍の実行速度向上が見込まれる
  • C言語で書かれたライブラリは依然スタックを消費する

本件コメント欄にて情報ご提示いただきました。ありがとうございます。