Can recursive loops be replaced with a conventional loop?
-
We were having a discussion in the office and someone asks why use recursion. He thinks you can replace recursion with a convetional loop, like a 'for' loop. I could not give him an answer. I think I should be able to give an intelligent answer, but I can't. So help me out. I know recursion can be expensive and my require a larger stack, but what are the benefits of one type of loop over the other, (if any)?
Thanks
-
@lazloman said:
We were having a discussion in the office and someone asks why use recursion. He thinks you can replace recursion with a convetional loop, like a 'for' loop. I could not give him an answer. I think I should be able to give an intelligent answer, but I can't. So help me out. I know recursion can be expensive and my require a larger stack, but what are the benefits of one type of loop over the other, (if any)?
Thanks
The answer is definitely yes, it's always possible (in all languages that do loops at all), but in many cases, you have to manage a stack on your own.
Why use recursion? Because in many cases, the algorithm is easier to write, read and understand that way.
-
Recursion is not a loop, recursion is recursion. If you don't need to worry about memory and have a solid grasp of the base case, then recursion will probably end up with shorter and more straightforward code. Otherwise, if you either need to keep memory under control or you just don't get recursion, use a loop. It will be more code, and more abstract than the original idea, but it will be less resource intesnive.
-
That's an usual academic problem. In some way, that reminds me a similar problem : event-driven VS thread-driven. In the second case, the system/language takes care of context-switching, your local variables are transparently saved. Same stuff happen with recursion : context variable stack up, you don't need to care, but at an extra price. But the two are always possible and interchangeable : either your programming environment takes care of it, or you have to handle dynamic structures yourself.
By transforming your recursion into a loop, you need to put your temp variables into a stack. As you care more about the stuff you keep in memory, you may realize you stack up unnecessary data which can be inferred : for example in a tree-visiting algorithm, you don't need to put the deepness level in a stack, you may as well increment or decrement the very same variable at each iteration. In complex algorithms it might require some mathematical factorization.
In the real world, when you happen to implement a recursive algorithm, ask to yourself if you really need a stack. If not, just make it a loop. If you still need a stack, make it a loop only if you need that amount of optimization ( that becomes rare and may lead to less readable code, so think twice ).
-
@lazloman said:
We were having a discussion in the office and someone asks why use recursion. He thinks you can replace recursion with a convetional loop, like a 'for' loop. I could not give him an answer. I think I should be able to give an intelligent answer, but I can't. So help me out. I know recursion can be expensive and my require a larger stack, but what are the benefits of one type of loop over the other, (if any)?
Thanks
It's always possible to turn recursion into iteration, but that doesn't mean it's simple, either to write or to read (tree traversal is a trivial problem to handle recursively, be it breadth-first or depth-first, and switching a recursive tree traversal from depth-first to breadth-first or the opposite is more or less trivial, doing so iteratively is much more difficult).
The fact is that some forms or recursion are "so trivial" to turn into iterative constructs that this has been baked in the compilers themselves: that's what tail-recursion is, a form of recursion trivially turned into an iterative construct.
Now while recursive solutions can be turned into iterative ones (and inversely), this doesn't mean that one isn't easier to do.
Some problems are inherently recursive (I already mentioned tree traversal), some structures are also inherently recursive (trees or linked lists are recursive construct, they therefore work really well with recursive algorithms), others are more iterative.
The main difference is that you don't think of them the same way, thinking recursively is usually clearer and conceptually simpler but it requires a certain frame of mind.
Basically, the main advantage of recursion is that it's easy to reason about (once you got the trick), easier to debug, much clearer to express and translate into code, while iteration is usually faster (our computers are all iterative).
This is why functional languages all implement tail-recursive optimization: they let you think recursively, but benefit from an iterative execution at the machine level (preventing stack-blowing and such)
-
Thanks for the replies. I knew recursion was more resource intensive, but I could not think of any significance between the two.
