超過Python樹遍歷遞歸深度

我有一個段樹保存數據範圍的數據（數據結構選擇here）。代碼如下：超過Python樹遍歷遞歸深度

class SegmentTree: 
    def __init__(self, N): 
     def _init(b, e): 
      if b is e: 
       data = foo() # No dependency 
       return Node(b, e, data, None, None) 
      else: 
       mid = (b + e)/2 

       L = _init(b, mid) 
       R = _init(mid + 1, e) 

       data = foo() #Data depends on L and R 

       return Node(b, e, data, L, R) 

     self.root = _init(1, N)

對於N在300附近，最大遞歸深度超過錯誤，此失敗。有沒有辦法迭代創建樹而不是遞歸？

來源

2011-10-09 knite

真正的問題不在於算法的遞歸深度，對於像300這樣的值，應該是大約10，但是您要將數字與is進行比較。該is關鍵字檢查對象的身份，而==檢查平等：

>>> 300 == 299+1 
True 
>>> 300 is 299+1 
False

因爲你if條件應當終止遞歸永遠不會爲真和功能將保持遞歸，即使b和e相等。

如果更改if這個問題就會消失：

if b == e: 
    ...

對於小的數字可能不會出現因爲Python "caches" and reuses the objects爲整數達到一定規模的問題。

來源

2011-10-09 17:42:16 sth

通常，您從遞歸轉換爲迭代的方式是手動維護堆棧（或隊列）。

喜歡的東西：

while stack is not empty: 
    item = pop from stack 

    do processing (such as adding onto the node) 

    push L and R onto the stack

堆棧並在內存中成長，因爲你如雨後春筍般冒出的每個項目，你正在推動兩項。

來源

2011-10-09 17:26:46

是的，我想這樣做，但我需要在（遞歸）創建L和R節點之後在當前節點上執行我的處理。我不確定在何處/如何將當前節點存儲以供將來處理 - 在單獨的堆棧上？ – knite

那麼通常有更好的方法來實現樹遍歷（儘管它們可以通過指針旋轉和東西變得複雜）而不是使用「棧」。畢竟，如果你在堆上使用堆棧，你實際上並沒有節省太多空間（除了一個常數因子，因爲你需要節省更少的狀態） – Voo

超過Python樹遍歷遞歸深度

回答

相關問題