可以回溯尾递归算法转换为迭代？ [英] Can a backtracking tail recursive algorithm be converted to iteration?

问题描述

让我们的骑士之旅的问题。这可以转换为迭代？什么是confunsing我是回溯的一部分。我如何走回头路在一个循环？我一定要一定要用一个堆栈数据结构实现回溯，当我去从递归迭代？

Let's take the Knight Tour problem. Can that be converted to iteration? What is confunsing me is the backtracking part. How do I backtrack in a loop? Do I have to necessarily use a stack data-structure to implement backtracking when I go from recursion to iteration?

我问这里有更好的方式了这个问题：<一href="http://stackoverflow.com/questions/13782410/can-someone-describe-through-$c$c-a-practical-example-of-backtracking-with-itera">Can通过codeA的实用性和迭代，而不是递归回溯的例子有人形容？

I asked this question in a better way here: Can someone describe through code a practical example of backtracking with iteration instead of recursion?

推荐答案

没有，那是不可能的。

No, it can't be.

所有的递归算法可以的执行的反复，通过模拟递归有一个明确的后进先出的数据结构。但是，这并不改变的算法的本身，即算法仍然递归的，不重复的。

All recursive algorithms can be implemented iteratively, by "emulating" recursion with an explicit LIFO data structure. But that does not change the algorithm itself, i.e. the algorithm remains recursive, not iterative.

同时，回溯是递归的固有属性。如果你有回溯，你有递归。正如你可能知道，一类算法，使简单的真正转化为迭代尾递归算法。但回溯的presence立即意味着你的递归是不是尾递归。

Meanwhile, backtracking is an inherent property of recursion. If you have backtracking, you have recursion. As you probably know, a class of algorithms that allows straightforward genuine conversion to iteration is tail-recursive algorithms. But the presence of backtracking immediately means that your recursion is not tail-recursion.

你可以做的是试图创造一个算法，不需要回溯。当然，这将是一个完全不同的算法，而不是原来的递归算法，以迭代形式下的转化率。

What you can do is to attempt to invent an algorithm that does not require backtracking. That, of course, will be a completely different algorithm, not a conversion of the original recursive algorithm to iterative form.

这篇关于可以回溯尾递归算法转换为迭代？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！