Pythonにおける再帰回数の上限について
研究室でプログラムを書いていたら遭遇したのでメモ。
シミュレーション用の環境を生成して、それをpickleモジュールを使ってシリアライズし保存しようとしていたところ、iPythonでは保存できるが、Pythonでは保存できないという問題に遭遇した。
関数の呼び出しを行う際には、スタック上にリターンアドレスや引数などが保存される。そのため、基本的にはただ大量に関数呼び出しを行っていくだけでもスタックを消費し、メモリを枯渇させることになる(末尾再帰最適化を行っている場合にはこの限りではない)。
この問題を引き起こさないようにするために、Pythonではスタックフレームの深さに上限を設けている。この上限は、 sys.getrecursionlimit()
で取得することができる。
以下の例は、スタックフレームの上限に引っかかる程度に再帰関数を実行する例である。この例を実行すると、設定されているrecursion limitの値と、実際にスタックフレームの上限に引っかかった時の様子が確認できる。Python 3.9.7では、デフォルトで1000に設定されている。1000回以上関数呼び出しをしたい場合は、 sys.setrecursionlimit()
を用いて明示的に上限を引き上げる必要がある。
import sys def f(x): return f(x - 1) if x != 0 else None d = sys.getrecursionlimit() print(d) f(d)
1000 Traceback (most recent call last): File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 8, in <module> f(d) File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 4, in f return f(x - 1) if x != 0 else None File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 4, in f return f(x - 1) if x != 0 else None File "/private/var/folders/s7/wxfjx1rj59ld0trt0wfqn3d40000gn/T/tmp.dXOnmfMy/main.py", line 4, in f return f(x - 1) if x != 0 else None [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded in comparison
先のプログラムを、iPython 7.27.0で実行してみると、recursion limitが3000になっていることが分かる。デフォルトで設定されているこの値が異なることによって、pickleモジュールでオブジェクトをシリアライズしようとした際に、iPythonではシリアライズできたが、Pythonではシリアライズできないという問題が発生した。