Can every recursive algorithm be rewritten iteratively? Can every iterative algorithm be rewritten recursively?
by 
EL1 2
ANSWERS: 5
-
Yes and yes, however, elegant looking recursive algorithms tend to look very ugly when written iteratively, and vice versa.
-
A recursive algorithm can be systematically written iteratively using an auxilliary stack. Essentially you simulate a recursive machine. An iterative algorithm can also be converted into a recursive algorithm systematically. Each looping construct can be replaced with a dedicated recursive function.
-
Good example of function that looks ugly when unwinded is Ackermann function, which traditional recursive form is simple and clear.
-
yes you can, but the question is what is more optimized?
-
Yes. "Any function that can be evaluated by a computer can be expressed in terms of recursive functions without the use of iteration, in continuation-passing style; and conversely any recursive function can be expressed in terms of iteration." Source and further information: http://en.wikipedia.org/wiki/Recursion_(computer_science%29
iwnit RELATED QUESTIONS
Copyright 2023, Wired Ivy, LLC