让我们以骑士巡游问题为例。这个问题能转换成迭代吗?困扰我的是回溯部分。在循环中如何回溯?当我从递归转换为迭代时,是否必须使用栈数据结构来实现回溯?
我更好地提出了这个问题:有人可以通过代码给出一个回溯的迭代实际示例而不是递归吗?
让我们以骑士巡游问题为例。这个问题能转换成迭代吗?困扰我的是回溯部分。在循环中如何回溯?当我从递归转换为迭代时,是否必须使用栈数据结构来实现回溯?
我更好地提出了这个问题:有人可以通过代码给出一个回溯的迭代实际示例而不是递归吗?
不行,这不可能。
所有递归算法都可以通过使用显式的LIFO数据结构“模拟”递归来以迭代方式实现。但这并不会改变算法本身,即算法仍然是递归的,而不是迭代的。
与此同时,回溯是递归的固有属性。如果存在回溯,那么就存在递归。正如您可能已经知道的,一类允许直接转换为迭代的算法是尾递归算法。但回溯的存在立即意味着您的递归不是尾递归。
您可以尝试发明一个不需要回溯的算法。当然,那将是完全不同的算法,而不是将原始递归算法转换为迭代形式。
编辑:(因为很明显你在谈论尾递归回溯,而不是简单的递归):
来自wikipedia:在计算机科学中,尾调用是在另一个过程内作为其最后一个动作发生的子例程调用
。据我所知,具有多个递归调用的函数-根据定义不是尾递归,而且由于回溯算法确实有多个调用,它们不是“尾递归”。