13

让我们来看看骑士巡回赛的问题。那可以转换为迭代吗？让我困惑的是回溯部分。如何在循环中回溯？当我从递归到迭代时，我是否必须使用堆栈数据结构来实现回溯？

我在这里以更好的方式问了这个问题：有人可以通过代码描述一个使用迭代而不是递归进行回溯的实际示例吗？

4

3 回答 3

25

不，不可能。

通过使用显式 LIFO 数据结构“模拟”递归，所有递归算法都可以迭代实现。但这不会改变算法本身，即算法保持递归，而不是迭代。

同时，回溯是递归的固有属性。如果你有回溯，你就有递归。您可能知道，允许直接真正转换为迭代的一类算法是尾递归算法。但是回溯的存在立即意味着您的递归不是尾递归。

您可以做的是尝试发明一种不需要回溯的算法。当然，这将是一个完全不同的算法，而不是将原始递归算法转换为迭代形式。

于 2012-12-08T22:11:36.147 回答
8

所有递归算法都可以转换为迭代算法，反之亦然。这是 Church-Turing 论文的直接结果。

它可能并不总是很明显（或微不足道），但任何算法都可以表示为递归或迭代过程；对于一般情况，这个问题之前已经回答过。

至于如何，有几种技术可以应用于从一种风格到另一种风格，例如看看这个答案，或者更详细的讨论阅读这篇解释如何使用堆栈来消除递归的文章。

于 2012-12-08T21:33:00.623 回答
3

基本上，每个递归都可以实现为循环+堆栈，因为它基本上是在机器（硬件）级别上实现的——只是一堆分支和一个用于存储返回地址和参数的堆栈。

在不满足条件时重复循环，而不是递归调用 - 只需将下一次迭代（可能还有最后一个状态）的参数推送到堆栈，然后返回循环的起点。

编辑：（因为很明显你在谈论尾递归回溯，而不是简单的递归）：

来自维基百科：In computer science, a tail call is a subroutine call that happens inside another procedure as its final action。据我所知，具有多个递归调用的函数 - 根据定义不是尾递归，并且由于回溯算法确实有不止一个调用，它们不是“尾递归”。

另请注意 - 只有循环和恒定空间的程序可以转换为在多项式时间内运行的第二个程序 P'（因为最多有2^CONST状态，基本上是CONST'，并且验证每一个都在多项式时间内完成- 所以总CONST'*p(n)时间，仍然是多项式），所以除非P=NP，这是不可能的，因为它允许我们通过将回溯解决方案转换为基于循环的多项式解决方案来在多项式时间内解决SAT 。（而且我相信进一步减少HP是可行的，以表明无论如何都不可能）。

于 2012-12-08T21:33:17.287 回答