+ 5

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

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 .

13th Mar 2018, 2:18 PM
Vaibhav Sharma
Vaibhav Sharma - avatar
7 Réponses
+ 19
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.
13th Mar 2018, 2:25 PM
Hatsy Rei
Hatsy Rei - avatar
+ 16
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
13th Mar 2018, 5:31 PM
Gaurav Agrawal
Gaurav Agrawal - avatar
+ 11
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
13th Mar 2018, 2:32 PM
John Wells
John Wells - avatar
+ 5
@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.
13th Mar 2018, 5:43 PM
John Wells
John Wells - avatar
+ 1
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.
23rd Mar 2019, 2:09 AM
Roger Greenlaw
+ 1
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!
25th Mar 2019, 9:18 AM
jcl
jcl - avatar
0
Gaurav Agrawal what would you prefer for segment tree, recursion algorithm or the iterative one.
23rd Mar 2019, 3:53 AM
Anurag Negi
Anurag Negi - avatar