recursion - 如何消除这种类型的递归？

Question

这比简单的左递归或尾调用递归要复杂一些。所以我想知道如何消除这种递归。正如您在下面看到的那样，我已经保留了自己的堆栈，因此该函数不需要参数或返回值。但是，它仍在将自己调高(或调低)到某个水平，我想将其变成一个循环，但我为此挠头了一段时间。

这是简化的测试用例，用 printf("dostuff at level #n") 消息替换所有“真实逻辑”。这是在 Go 中，但问题适用于大多数语言。使用循环和 goto 是完全可以接受的(但我玩过这个并且它变得令人费解，失控并且看起来不可行);但是，应避免使用额外的辅助函数。我想我应该把它变成某种简单的状态机，但是……哪个？ ;)

至于实用性，这是以每秒大约 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()
    }

更新——经过这里的一些讨论和进一步思考:

我刚刚编写了以下伪代码，理论上应该做我需要的事情:

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--
    }
}

当然，棘手的部分是为我的自定义用例填写 nextsibling()。但是，作为消除内部递归同时保持我需要的深度优先遍历顺序的通用解决方案，这个粗略的大纲应该以某种形式实现。

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
  }
}

注意:这将深入结构。如果这不是您想要的，则需要进行一些修改。