回溯算法是否总是使用递归？

Question

回溯算法是否总是使用递归？

algorithmrecursionbacktracking

3

我迄今使用的所有回溯算法都是基于递归的。但我找不到任何证据表明回溯不能是非递归的。那么问题是，回溯算法是否总是使用递归？

- GraphLearner

14

每个递归算法都可以自动转换为非递归算法：只需将你本来要推入/弹出的数据从调用堆栈改为常规堆栈中的推入/弹出操作即可。 - undefined

2

递归只是一种实现方式而已。它非常适合用于回溯，这也是为什么你通常会在那些算法中看到递归的原因。然而，正如@WillemVanOnsem所说，没有人强迫你使用递归来实现它。 - undefined

1

https://en.wikipedia.org/wiki/Backtracking#Description_of_the_method - undefined

迭代版本的网格A*回溯算法，没有任何递归...它是一个简单的O(n)循环，没有任何堆栈... - undefined

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tyler Liu · Accepted Answer

不需要使用递归就可以进行回溯。这里有一个例子：使用堆栈的非递归回溯：

boolean solve(Node n) {
    put node n on the stack;
    while the stack is not empty {
        if the node at the top of the stack is a leaf {
            if it is a goal node, return true
            else pop it off the stack
        }
        else {
            if the node at the top of the stack has untried children
                push the next untried child onto the stack
            else pop the node off the stack

    }
    return false
}

一个真实的例子

N皇后问题

根据我的测试，非递归解法明显更快。我并不是说非递归解法总是更快，但它确实提供了更多性能优化的灵活性（你可以决定将什么放入堆栈，而不是保存整个调用栈）。