I am trying to do work with examples on Trees as given here: http://cslibrary.stanford.edu/110/BinaryTrees.html These examples all solve problems via recursion, I wonder if we can provide a iterative solution for each one of them, meaning, can we always be sure that a problem which can be solved by recursion will also have a iterative solution, in general. If not, what example can we give to show a problem which can be solved only by recursion/Iteration?
--
Recursion has the advantage where it will continue without a known end. A perfect example of this is a tuned and threaded Quick Sort.
You can't spawn additional loops, but you can spawn new threads via recursion.
In my experience, most recursive solution can indeed be solved iteratively.
It is also a good technique to have, as recursive solutions may have too large an overhead in memory and CPU consumptions.
The only difference between iteration and recursion on a computer is whether you use the built-in stack or a user-defined stack. So they are equivalent.
Since recursion uses an implicit stack on which it stores information about each call, you can always implement that stack yourself and avoid the recursive calls. So yes, every recursive solution can be transformed into an iterative one.
Read this question for a proof.
Recursion and iteration are two tools that, at a very fundamental level, do the same thing: execute a repeated operation over a defined set of values. They are interchangeable in that there is no problem that cannot, in some way, be solved by only one of them. That does not mean, however, that one cannot be more suited than the other.
As an "old guy," I fall back to my memory of learning that recursive descent parsers are easier to write, but that stack-based, iterative parsers perform better. Here's an article that seems to support that idea with metrics:
One thing to note is the author's mention of overrunning the call stack with recursive descent. An iterative, stack-based implementation can be much more efficient of resources.