0

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

这是简化的测试用例，用 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() 。但就像在保持我需要的深度优先遍历顺序的同时消除内部递归的一般解决方案一样，这个粗略的轮廓应该以某种形式这样做。

4

1 回答 1

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

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

于 2012-04-05T03:43:16.983 回答