1

我有以下递归 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
}

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

4

3 回答 3

2

我认为您上面的代码是一种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
}
于 2013-11-11T16:28:58.233 回答
0

Tom Moertel 在他的博客上写了这个问题的解决方案。
他清楚地解释了递归函数到迭代（链接）的转换。

当我需要时，我已经使用他的方法来改变我自己的功能，并且我确信这是正确的。

我希望这会有所帮助。

于 2013-11-11T16:03:03.210 回答
0

基本上要将递归函数转换为迭代函数，您应该注意哪个是案例库（这种情况是递归函数的停止案例），将所有功能放入一个循环并将该基本案例用作已用循环的退出条件。

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

于 2013-11-11T15:45:01.503 回答