Menu
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?
I asked this question in a better way here: Can someone describe through code a practical example of backtracking with iteration instead of recursion?
261
Every recursive function can be transformed into an iterative function by replacing recursive calls with iterative control constructs and simulating the call stack with a stack explicitly managed by the program.
Which data structure is best suited for converting recursive implementation to iterative implementation of an algorithm? Explanation: Since function calls are executed in Last In First Out order, stack is the data structure for converting recursive to iterative implementation.
No, it is not possible to express all recursion as tail recursion unless you do supplement the tail recursion with other control flow mechanisms.
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.
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.
71
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
