Python 3.11以前では、Pythonレベルの再帰はCレベルの再帰を常に引き起こしていました。
ですので、Pythonの再帰の深さはCレベルのスタックの大きさに依存していました。
Linuxではスタックは動的に増加出来るのですが、Windowsでは出来ません。
下記の深い再帰は、WindowsではPython 3.10はスタックオーバーフローを起こします。
import sys
sys.setrecursionlimit(100_000)
def foo(n):
return 0 if n == 0 else foo(n-1) + 1
print(foo(10_000)) # Process finished with exit code -1073741571 (0xC00000FD)
再帰を前提とするプログラムで、デフォルトのスタックサイズでは再帰の深さが足りない場合、スタックサイズを最大値に指定したスレッドを一つ作成して、そのスレッドで再帰を実行するなどの対応が必要でした。
Python 3.11では、"純粋な"Pythonレベルの再帰はCレベルの再帰を生成しなくなりました。このため、上記のプログラムは、Windows上でも成功するようになりました。しかし、下記のように__call__メソッドは内部でCレベルの再帰を作成しているようで、3.11でもスタックオーバーフローを起こします。
import sys
sys.setrecursionlimit(100_000)
class Foo:
def __call__(self, n):
return 0 if n == 0 else self(n - 1) + 1
print(Foo()(10_000)) # Process finished with exit code -1073741571 (0xC00000FD)
Python 3.12では、C-レベルの再帰の上限が導入され、CPythonの内部で値がハードコードされました。その結果、スタックオーバーフローになる前に、かなり浅い段階でPythonのRecursionErrorで止まるようになりました。
Traceback (most recent call last):
File "C:\Users\xxx\temp5.py", line 11, in <module>
print(Foo()(10_000))
^^^^^^^^^^^^^
File "C:\Users\xxx\temp5.py", line 8, in __call__
return 0 if n == 0 else self(n - 1) + 1
^^^^^^^^^^^
File "C:\Users\xxx\temp5.py", line 8, in __call__
return 0 if n == 0 else self(n - 1) + 1
^^^^^^^^^^^
File "C:\Users\xxx\temp5.py", line 8, in __call__
return 0 if n == 0 else self(n - 1) + 1
^^^^^^^^^^^
[Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded
Process finished with exit code 1
この変更を実装したMark Shannonの理由としては、
- Pure Pythonの再帰がPythonの再帰と分離されたのだから、以前からあったPure Pythonの再帰上限とは別に、Cレベルの上限を設定すべき。
- スタックオーバーフローは好ましくない。
- スタックサイズはプラットフォームごとに仕様が異なるので、とりあえずどのサポートされているプラットフォームでもオーバーフローしない小さい値に上限を設定する。
という理由でした。
この仕様は、深いＣレベルの再帰が可能であったLinuxなど、Cのスタックサイズが十分にあう場合でも新規の浅い上限でRecursionErrorとなるため、Memoizationを提供するfunctoolsのcacheなど再帰を前提とするプログラムでCレベルの再帰を使用するプログラムに致命的な支障をきたすため、反対意見が出されています。
Mark Shannonは、3.12.0での上限は保守的過ぎたため、実際はもっと高い値に設定可能であり変更をコミットしています。また将来的には、スタックサイズを事前に把握し、スタックオーバーフローを起こさない程度まで動的にリミットを設定出来るように改善したい、としています。