递归函数到非递归函数？

Question

我有以下递归Grails函数：

private boolean isCyclic(TreeNode node) {
    boolean cyclic = false
    def myParents = this.parents

    // if there are parents of this node
    if (myParents.size() != 0) {

        // if the new node is in the parents set of this node
        if (myParents.contains(node)) {
            cyclic = true
            return cyclic
        }
        else {
            // go into each parent of this node and test if new node is contained in their parents
            myParents.each { parent ->
                log.debug "go to parent: "+parent.name
                if (cyclic) {
                    return cyclic
                }
                cyclic = parent.isCyclic(node)
            }
        }
    }

    return cyclic
}

如何将此函数转换为非递归函数？

Answer 1

我认为上面的代码是一个contains方法，而不是循环检查.

但是，下面是一个包含方法和循环检查的快速例子，它采用迭代的方式.祈祷他们是对的

def contains( TreeNode node ) {
    // if this node is the one we're looking for, return true
    if( node == this ) {
        return true
    }
    // A queue of nodes to work on
    def parentQueue = this.parents as Queue

    // A set of nodes we've seen (to avoid loops)
    def seen = [ this ] as Set

    // While we have nodes to look for
    while( parentQueue ) {
        // get the next node
        def next = parentQueue.pop()

        // Check if it's the one we're looking for
        if( next == node ) return true

        // And if not, add it's parents to the queue
        // assuming we've not seen it before
        if( !seen.contains( next ) ) {
            next.parents.each { parentQueue.offer( it ) }
        }
    }
    // Not found
    return false
}

def isCyclic() {
    // A queue of nodes to work on
    def parentQueue = this.parents as Queue

    // A set of nodes we've seen (to detect loops)
    def seen = [ this ] as Set

    // While we have nodes to look for
    while( parentQueue ) {
        // Look at the next element in the queue
        def next = parentQueue.pop()

        // If we've seen it before, it's cyclic
        if( seen.contains( next ) ) return true

        // Otherwise, record we've seen this node
        seen << next

        // And add its parents tothe queue
        next.parents.each { parentQueue.offer( it ) }
    }
    // All done, not cyclic
    return false
}

Answer 2

基本上，要将递归函数转换为迭代函数，您应该注意到它是case基(这里是递归函数的停止情况)，将所有功能放在一个循环中，并使用这个基本情况作为用过的循环的退出条件。

也许我没有很好地解释它，但是每个递归函数都有一个迭代函数。

Answer 3

汤姆·莫特尔( Tom )在他的博客上为这个问题写了解决方案。

他清楚地解释了将递归函数转换为迭代(链接)的过程。

当我需要的时候，我用他的方法来转换我自己的功能，我确信这是正确的。

我希望这能帮上忙。