是否可以使用迭代器實現遞歸算法？

Question

我已經給樹是這樣的：

http://www.seqan.de/dddoc/html/streePreorder.png http://www.seqan.de/dddoc/html/streePreorder.png

我可以存取權限的每個節點的下一個操作。

// postorder dfs 
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex); 
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator 

但我想在樹上使用遞歸算法。
有沒有辦法讓遞歸算法（排除每個節點上最大的子樹）迭代？
或我如何非遞歸地訪問元素？

編輯： 企業的實際問題：
我已經給了遞歸算法，即在樹上的作品。 （遞歸）
我也使用庫，我只能用迭代器訪問項目（非標準，迭代）

遞歸< - >迭代。
我該如何解決這個問題？

Answer 1

如果你的迭代器只支持向前遍歷（可能是向後），但不遵循樹上的鏈接或快速隨機訪問，你將很難適應樹算法。然而，最終，任何答案都將取決於您的自定義迭代器提供的界面，而這些界面並未提供。

例如，考慮樹搜索的簡單算法。如果迭代器提供的唯一操作是「從第一個元素開始並逐個移動」，那麼顯然無法高效地執行樹搜索。你也不能實現二分查找。因此，您必須準確提供支持哪些操作的列表，以及（關鍵）每種操作的複雜性。

Answer 2

任何遞歸函數都可以用堆棧實現。如果這是你問的問題。

這是關於這個問題的article by Phil Haack。

性能收益是一種或另一種是推測性的，編譯器會在我們後面的代碼中執行一些無法預測的代碼。實現兩個並獲得一些實數。如果他們是相似的使用你發現更可讀的。

Answer 3

你可以將的遞歸函數轉換爲迭代函數的幫助。

//breadth first traversal pseudo-code 
push root to a stack 
while(stack isn't empty) 
    pop element off stack 
    push children 
    perform action on current node 

取決於您想要遍歷節點的方式，實現將有所不同。所有遞歸函數都可以轉換爲迭代函數。關於如何要求關於具體問題的信息的一般用法。使用堆棧/隊列並轉換爲for循環是應該解決大多數情況的常用方法。

您還應該考慮尾遞歸以及如何識別它們，因爲這些問題可以很好地轉化爲for循環，許多編譯器甚至爲您執行此操作。

一些更具數學導向的遞歸調用可以通過recurrence relations來解決。你遇到這些尚未解決的可能性不太可能，但它可能會讓你感興趣。

//編輯，性能？ 真的取決於你的實現和樹的大小。如果在遞歸調用中存在很多深度，那麼您將得到堆棧溢出，而迭代版本將執行正常。我會更好地掌握遞歸（如何使用內存），並且您應該能夠決定哪種方法更適合您的情況。 Here is an example of this type of analysis with the fibonacci numbers。

Answer 4

即使使用遞歸迭代，您最終還是會得到每個節點的節點訪問權限。我需要知道的是：我的迭代器如何被告知先深入，然後：我將如何被通知一個級別已經開始/結束（即遞歸步驟的開始/結束）。

該知識可以映射到遞歸算法。