可以将回溯尾递归算法转换为迭代吗？

Question

让我们来看看Knight Tour问题吧.可以转换为迭代吗？困扰我的是回溯部分.如何在循环中回溯？当我从递归到迭代时,是否必须使用堆栈数据结构来实现回溯？

---

我在这里以更好的方式问了这个问题:有人能通过代码描述一个回溯迭代而不是递归的实际例子吗？

Answer 1

不,它不可能.

通过使用显式LIFO数据结构"模拟"递归,可以迭代地实现所有递归算法.但这并没有改变算法本身,即算法仍然是递归的,而不是迭代的.

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

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

Answer 2

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

它可能并不总是显而易见(或微不足道),但任何算法都可以表示为递归或迭代过程; 对于一般情况,此问题之前已得到解答.

至于如何,有几种方法可以适用于打算从一个风格到其他,比如看看这个答案,或更详细的讨论阅读此文章解释如何使用堆栈来消除递归.