Do all recursion based algorithms can be converted into iterative (loop based) algorithms?

Question

As in case of finding factorial of a number or fibonacci series , we can write both recursion based and loop based solutions . Is recursion always convertible to loop based solution? If not , please give example .

Answer 1

I have yet to see someone traversing an entire binary tree using only iteration, IRL. Ofc it's possible, but why would you hurt yourself.

Anyway, this should answer your question:
https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

The short answer is yes. A Turing machine (the basis of imperative programming) and the lambda calculus (the basis of functional programming), both models of universal computing, is equivalent in power. Hence, every recursive function has an iterative counterpart.

Answer 2

sometimes it become very hard to convert recursion to loop , I used recursion only in some competitive programming questions ... can't able to think how to convert that recursion to loop

Answer 3

Every loop can be made recursive and every recursion can be turned into a loop. However, there are times that one is much easier to implement over the other and, therefore, you should code that method.

https://www.sololearn.com/Discuss/1109789

Answer 4

@Gaurav check out my Ackermann code in my link. Something like it works for every recursion, but it is much more complex than the recusive solution. I could do Hatsy's binary tree with that, but the recursive code is so much easier to write nobody would bother. Except for the reason I wrote that code, to prove the point it is doable.

Answer 5

As above, either loops or recursion can be used to program repetitive operations. It is sometimes simpler to use loops and sometimes recursion is better. Most importantly, the amounts and type of memory available and programmer skill should be used to determine which is best.

Answer 6

Hatsy Rei
Your link took me on a long theoretical journey ... and I understood that, practically, choosing between iteration and recursion isn't 'necessarily' a trivial question!

Answer 7

Gaurav Agrawal what would you prefer for segment tree, recursion algorithm or the iterative one.