如何消除這種類型的遞歸？

Question

這比簡單的左遞歸或尾部遞歸遞歸有點複雜。所以我想知道如何消除這種遞歸。我已經保留了自己的棧，如下所示，所以函數不需要參數或返回值。然而，它仍然將自己調高（或減小）到一定的水平，我想把它變成一個循環，但一段時間以來我一直在撓頭。

下面是簡化的測試用例，用printf（「級別爲#n的dostuff」）消息替換所有「真實邏輯」。這是在Go中，但該問題適用於大多數語言。使用循環和goto's將是完全可以接受的（但我玩過這個，它變得複雜，非常奇怪，並且看起來不可行）。然而，應該避免額外的輔助函數。我想我應該把它變成某種簡單的狀態機，但是......哪個？ ;）

至於實用性，這是每秒運行約2000萬次（堆棧深度範圍可以從1到最大25）。這是維護我自己的堆棧必然比函數調用堆棧更穩定/更快的一種情況。 （在這個函數中沒有其他函數調用，只有計算。）另外，沒有生成垃圾=沒有垃圾收集。

所以這裏有雲：

func testRecursion() { 
    var root *TMyTreeNode = makeSomeDeepTreeStructure() 
    // rl: current recursion level 
    // ml: max recursion level 
    var rl, ml = 0, root.MaxDepth 
    // node: "the stack" 
    var node = make([]*TMyTreeNode, ml + 1) 

    // the recursive and the non-recursive/iterative test functions: 
    var walkNodeRec, walkNodeIt func(); 

    walkNodeIt = func() { 
     log.Panicf("YOUR ITERATIVE/NON-RECURSIVE IDEAS HERE") 
    } 

    walkNodeRec = func() { 
     log.Printf("ENTER LEVEL %v", rl) 
     if (node[rl].Level == ml) || (node[rl].ChildNodes == nil) { 
      log.Printf("EXIT LEVEL %v", rl) 
      return 
     } 
     log.Printf("PRE-STUFF LEVEL %v", rl) 
     for i := 0; i < 3; i++ { 
      switch i { 
      case 0: 
       log.Printf("PRECASE %v.%v", rl, i) 
       node[rl + 1] = node[rl].ChildNodes[rl + i]; rl++; walkNodeRec(); rl-- 
       log.Printf("POSTCASE %v.%v", rl, i) 
      case 1: 
       log.Printf("PRECASE %v.%v", rl, i) 
       node[rl + 1] = node[rl].ChildNodes[rl + i]; rl++; walkNodeRec(); rl-- 
       log.Printf("POSTCASE %v.%v", rl, i) 
      case 2: 
       log.Printf("PRECASE %v.%v", rl, i) 
       node[rl + 1] = node[rl].ChildNodes[rl + i]; rl++; walkNodeRec(); rl-- 
       log.Printf("POSTCASE %v.%v", rl, i) 
      } 
     } 
    } 

    // test recursion for reference: 
    if true { 
     rl, node[0] = 0, root 
     log.Printf("\n\n=========>RECURSIVE ML=%v:", ml) 
     walkNodeRec() 
    } 

    // test non-recursion, output should be identical 
    if true { 
     rl, node[0] = 0, root 
     log.Printf("\n\n=========>ITERATIVE ML=%v:", ml) 
     walkNodeIt() 
    } 

}

UPDATE - 經過一番討論，在這裏，和進一步的思考：

我只是做了下面的僞代碼在理論上應該做我需要的東西：

curLevel = 0 
for { 
    cn = nextsibling(curLevel, coords) 
    lastnode[curlevel] = cn 
    if cn < 8 { 
     if isleaf { 
      process() 
     } else { 
      curLevel++ 
     } 
    } else if curLevel == 0 { 
     break 
    } else { 
     curLevel-- 
    } 
} 

當然，棘手的部分將填充我的自定義用例的nextcond（）。但是，作爲一種消除內部遞歸的一般解決方案，同時保持我需要的深度優先遍歷順序，這個粗略輪廓應該以某種形式或另一種形式進行。

Answer 1

我不太確定我明白你想做什麼，因爲你的遞歸代碼看起來有點奇怪。但是，如果我理解了TMyTreeNode的結構，那麼這就是我爲非遞歸版本所做的。

// root is our root node 
q := []*TMyTreeNode{root} 
processed := make(map[*TMyTreeNode]bool 
for { 
    l := len(q) 
    if l < 1 { 
    break // our queue is empty 
    } 
    curr := q[l - 1] 
    if !processed[curr] && len(curr.childNodes) > 0 { 
    // do something with curr 
    processed[curr] = true 
    q = append(q, curr.childNodes...) 
    continue // continue on down the tree. 
    } else { 
    // do something with curr 
    processed[curr] = true 
    q := q[:l-2] // pop current off the queue 
    } 
} 

注意：這將任意深入結構。如果這不是你想要的，它將需要一些修改。