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

Question

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

---

我在这里以更好的方式问了这个问题:Can someone describe through code a practical example of backtracking with iteration instead of recursion?

Answer 1

不，这不可能。

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

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

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