Menu
As far as I know, most recursive functions can be rewritten using loops. Some may be harder than others, but most of them can be rewritten.
Under which conditions does it become impossible to rewrite a recursive function using a loop (if such conditions exist)?
755
So, yes all-recursive code can be converted to iteration.
Explanation: There is nothing recursion can compute that looping can't, but looping takes a lot more plumbing. Therefore, the one thing recursion can do that loops can't is make some tasks super easy.
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.
When you use a function recursively, the compiler takes care of stack management for you, which is what makes recursion possible. Anything you can do recursively, you can do by managing a stack yourself (for indirect recursion, you just have to make sure your different functions share that stack).
So, no, there is nothing that can be done with recursion and that cannot be done with a loop and a stack.
67
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
