Pythonの再帰の落とし穴

Pythonの再帰呼び出しの落とし穴

競技プログラミングでPython3を使用してDFSしたときに再帰の深さ制限が思ったよりもきつく，ハマってしまったので記録として残しておく．
PythonでDFSするときにはこの設定を気にしたい.

再帰の深さ制限の確認と変更

• 確認

>>> sys.getrecursionlimit()
1000

• 変更

>>> sys.setrecursionlimit(1000000)
>>> sys.getrecursionlimit()
1000000

デバッグ時の注意

AtCoderで使用できるPython3.4.3と3.6や3.7で再帰の制限を超えた時のエラー内容が異なる．
バグの可能性のある箇所を例外処理でキャッチしてデバッグするときには気をつける必要がある．

• 検証用プログラム

def func():
    func()
try:
    func()
except Exception as e:
    print(type(e),e)

• 出力: Python3.4.3

<class 'RuntimeError'> maximum recursion depth exceeded

• 出力: Python3.6.1

<class 'RecursionError'> maximum recursion depth exceeded