【再帰】Python3の個人的つまずきポイント その２

初めに

• 不定期に備忘録を投稿します。
  • その１【二次元リストの初期化】

使用Version：Python 3.11.2

再帰の深さ上限の拡張

Python3における再帰関数の実行回数の上限は1000です。
1000回というのはデフォルト設定であり、1000回を超える実行を可能にするためには別途下記のように記述する必要があります。

import sys

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

paizaのS,Aランクの問題では、境界値のテストケースにおいて再帰関数を数千～数万回実行する場合があるかもしれません。
再帰関数を定義した際には必要に応じて下記の処理を記載します。

Python 3.11.2 ドキュメントには以下のように記載されています。
無制限に拡張できるわけではないため、やみくもに大きい値を設定するのは避けるべきです。

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

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

実験

再帰関数の実行上限を体感するために以下のサンプルコードで実験してみます。
再帰回数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()

実行結果は以下の通りです。

test.py実行結果のログ

■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が出ました。
  • 1000回実行の前にエラーが出ている理由ですが、sys.getrecursionlimit()で取得できる値が厳密には「Pythonインタープリタのスタックの深さの最大値」であるためです。（参考）
• sys.setrecursionlimit(10000)で再帰関数の実行回数上限を増やすとRecursionErrorを出すことなく実行完了できます。

Python3.10までは、より厳密に再帰関数の実行回数の上限拡張に対応するためにはthreading.stack_size()で実際にスタックとして使える領域の容量も設定する必要がありました。
（参考）

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言語で書かれたライブラリは依然スタックを消費します。
  • 本件コメント欄にて情報ご提示いただきました。ありがとうございます。
• 少なくともpaiza上ではsys.setrecursionlimit()さえ使えばランタイムエラーを避けられると思います。
  • もちろん、なるべく実行回数を削減できるように実装することが前提です。
  • 2023/03/18現在、paiza上のPython3のバージョンは3.8.10です。
  • https://paiza.jp/guide/language