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

:::note info
使用言語：Python 3.11.2
:::

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

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

## 実験
再帰回数の上限が995～998回となる場合
```Python3: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インタープリタのスタックの深さの最大値」であるため
  - [参考](https://stackoverflow.com/questions/38265839/max-recursion-is-not-exactly-what-sys-getrecursionlimit-claims-how-come/38265931#38265931)
- `sys.setrecursionlimit(10000);`したあとはRecursionErrorがスローされない

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

:::note warn 
[公式ドキュメント](https://docs.python.org/ja/3.11/library/sys.html#sys.setrecursionlimit)には以下のように記載されている

> Python インタプリタの、スタックの最大の深さを limit に設定します。この制限は Python プログラムが無限に再帰し、 C スタックがオーバーフローしてクラッシュすることを防止するために設けられています。
> 
> limit の最大値はプラットフォームによって異なります。深い再帰処理が必要な場合にはプラットフォームがサポートしている範囲内でより大きな値を指定することができますが、この値が大きすぎればクラッシュするので注意が必要です。
:::

## 補足2

かつてはスタック領域の容量も別途設定する必要があった
Python3.10までは `threading.stack_size()` を使うことで対応 （[参考](https://www.yukiyukiponsu.work/entry/python-recursion-error#maximum-recursion-depth-exceeded%E3%81%AE%E8%A7%A3%E6%B1%BA%E7%AD%96)）
```python3
import sys
import threading

# 再帰回数上限値のセット。引数にはPythonインタープリタのスタックの深さを指定する
sys.setrecursionlimit(67108864)
#　2^20のstackメモリを確保
threading.stack_size(1024*1024)
```
- Python3.11からは[Pythonで書いた関数の再帰ではスタックを消費しなくなった](https://docs.python.org/ja/3/whatsnew/3.11.html#inlined-python-function-calls)
  - フィボナッチや階乗について約1.7倍の実行速度向上が見込まれる
  - C言語で書かれたライブラリは依然スタックを消費する

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