首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >回溯算法总是使用递归吗?

回溯算法总是使用递归吗?
EN

Stack Overflow用户
提问于 2017-09-07 10:29:49
回答 1查看 1.2K关注 0票数 1

我到目前为止使用的所有回溯算法都是基于递归的。但我没能找到任何证据证明回溯不能是非递归的。那么问题是,回溯算法是否总是使用递归?

EN

回答 1

Stack Overflow用户

发布于 2022-02-15 20:11:14

不,回溯可以不用递归完成。下面是一个例子:非递归回溯,使用堆栈

代码语言:javascript
复制
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
}

一个真实的例子

问题

正如我所测试的,非递归解决方案的速度要快得多。我并不是说非递归解决方案总是更快,但它确实为性能优化提供了更大的灵活性(而不是保存整个调用堆栈,而是决定将什么放入堆栈中)。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/46094082

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档