Is it possible to convert a recursive algorithm to go back to iteration?

Question

Take the problem of a knightly tour. Could this be converted to iteration? What bothers me is rollback. How do I retreat in a loop? Should I use the stack data structure to implement the countdown when I go from recursion to iteration?

---

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

Answer 1

No, that cannot be.

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

Meanwhile, backtracking is an essential property of recursion. If you have a rollback, you have a recursion. As you probably know, the class of algorithms that allows direct genuine conversion to iteration is a tail-recursive algorithm. But having a countdown immediately means that your recursion is not tail recursion.

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

Answer 2

All recursive algorithms can be converted to iterative algorithms and vice versa. This is a direct result of the Turing Church.

This may not always be obvious (or trivial), but any algorithm can be expressed as a recursive or as an iterative process; for the general case, this question was answered before .

Regarding the method, there are several methods that can be used to move from one style to another, for example, look at this answer or for a more detailed discussion read this article , which explains how to use stacks to eliminate recursion.

Answer 3

In principle, each recursion can be implemented as a + stack cycle, because the fact that it is mainly implemented at the machine (hardware) level is just a bunch of branches and a stack for storing return addresses and arguments.

Take a loop that repeats until the condition is met, and instead of the recursive invokation, just push the parameters for the next iterations (and possibly the last state) onto the stack, and return to the starting point of the loop.

---

EDIT: (since it is clear that you are talking about a tail recursive backtrack, not a simple recursion):

From wikipedia : In computer science, a tail call is a subroutine call that happens inside another procedure as its final action . As far as I know, a function with several recursive calls is not tail recursion by definition , and since backtracking algorithms have more than one call, they are not tail recursive.

Also note that a program that has only loops and constant space can be transferred to the second program P ', which runs in polynomial time (since there are no more than 2^CONST states, which is basically CONST' , and checking each of them is executed during polynomial time, therefore, the results of CONST'*p(n) time, which is still polynomial), therefore , if P=NP , this is not possible , as this will allow us to solve SAT in polynomial time, translating the solution of inverse tracking into a loop based polynomial. (And I believe that a further reduction from HP is possible to show that this is impossible anyway).