Python中的遞歸有多安全？

Question

我正在從事AI作業，儘管我的教授提出了建議，但我無意在lisp中編寫此作業。不過，我想做想遞歸寫，最好保持簡潔。這裏是我的問題：

我正在運行用完堆棧空間的一大風險，如果我進行了一個大的狀態空間搜索？ Python堆棧有多深？

Answer 1

有多深不Python的堆棧去？

Python中默認的遞歸限制是1000幀。您可以使用sys.setrecursionlimit(n)來改變這一點，風險自負。

如果您在使用python設置，我會建議使用更適合的語言模式。如果你想使用遞歸式的搜索，並需要任意堆棧的深度，你可以使用Python的增強型發生器（協程）來創建一個「蹦牀模式」（在PEP342有一個例子）

，儘管我教授的建議，我無意寫這個任務在lisp

如果練習的目的是基於遞歸的，tail-call優化語言，如lisp，可能是你最好的選擇。

Answer 2

遞歸在Python（CPython的，這是）不能超過sys.getrecursionlimit()走得更深。您可以使用sys.setrecursionlimit將此限制設置爲不同的值。

我看到三個選項：

1. 使用Lisp語言畢竟，它是遞歸的問題，優化（與智能Lisp語言的編譯器將消除尾遞歸）
2. 在遞歸函數設置遞歸限制得到無限遞歸（在程序飲食flaming death的風險）
3. 使用迭代有一個明確的堆棧。一個簡單的list會做。 append被推，pop被彈出。

Answer 3

>>> i=0 
>>> def a(): 
...  global i 
...  i += 1 
...  try: 
...    a() 
...  except: 
...    print(i) 
... 
>>> a() 
999 
>>> import sys 
>>> sys.getrecursionlimit() 
1000 

不知道是否有幫助

Answer 4

Python的限制遞歸值的深度可以通過調用sys.setrecursionlimit調用sys.getrecursionlimit和變化找出。默認值不是很大。如果將它設置的太高，那麼當Python遞歸時，最終可能會吹出C堆棧。雖然默認值在所有平臺上都應該是安全的（你得到一個Python異常而不是崩潰），但是「太高」依賴於平臺。

有語言，使有關尾調用優化了有力保障。 Scheme是最着名的例子;這是一個Lisp方言。不管你有多麼不喜歡你的教授，你都應該考慮學習至少一種類似Lisp的語言。

Answer 5

正如其他人所指出的那樣，儘管存在C棧溢出的風險（假設您正在使用CPython），但您可以使用sys.setrecursiondepth()來增加遞歸深度。如果遇到這個問題，您可以通過調用thread.stack_size()新的堆棧大小來創建堆棧大小更大的線程，然後生成一個新線程來完成實際工作。