一个采用回溯和尾递归的算法能否被转换成迭代算法？

Question

一个采用回溯和尾递归的算法能否被转换成迭代算法？

algorithmdata-structuresrecursiontail-recursion

20

让我们以骑士巡游问题为例。这个问题能转换成迭代吗？困扰我的是回溯部分。在循环中如何回溯？当我从递归转换为迭代时，是否必须使用栈数据结构来实现回溯？

我更好地提出了这个问题：有人可以通过代码给出一个回溯的迭代实际示例而不是递归吗？

- chrisapotek

3个回答

11

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

可能并不总是显而易见（或微不足道），但任何算法都可以表达为递归或迭代过程；对于一般情况，这个问题已经在before中得到了回答。

至于如何进行转换，有几种技术可以应用于从一种风格转换到另一种风格，例如查看this答案，或者阅读this文章，其中解释了如何使用堆栈来消除递归。

- Óscar López

10

“Church-Turing论题的直接结果”是任何递归算法都允许迭代实现。它并不以任何方式声称任何递归算法都可以转换为迭代算法。此外，正确的答案是否定的，通常是不可能的。理解算法和其实现之间的区别是关键时刻。没有这一点，它就会变成无用的学究式陈述。 - AnT stands with Russia

3

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

有一个循环，当条件未满足时重复执行，而不是进行递归调用 - 只需将下一次迭代的参数（以及可能的最后状态）推送到堆栈中，并返回到循环的起始点。

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

来自wikipedia：在计算机科学中，尾调用是在另一个过程内作为其最后一个动作发生的子例程调用。据我所知，具有多个递归调用的函数-根据定义不是尾递归，而且由于回溯算法确实有多个调用，它们不是“尾递归”。

同时需要注意的是 - 一个只包含循环和恒定空间的程序可以被翻译成第二个程序P'，该程序可以在多项式时间内运行（因为最多有2 ^ CONST个状态，基本上是CONST'，并且验证每个状态都可以在多项式时间内完成 - 因此总共需要CONST' * p(n)时间，这仍然是多项式时间），所以除非P = NP，否则不可能，因为这将使我们能够通过将回溯解决方案翻译为基于循环的多项式解决方案，在多项式时间内解决SAT问题（我相信从HP进行进一步缩减以显示它是不可能的）。

- amit

我对“如何做到”的内容更感兴趣。 - chrisapotek

@chrisapotek：循环的第二部分回答了如何完成 - 具体细节取决于实现 - 但这是一般指南 - 只需将要搜索的下一个状态推送到堆栈中（在骑士周游问题中，从每个步骤插入所有可能的新步骤进行搜索，并返回循环的起始点） - amit

@chrisapotek：我想我最初误解了你的真正意图。这次修改是否更好地回答了你的问题？ - amit

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

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

- AnT stands with Russia · Accepted Answer

不行，这不可能。

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

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

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