Recursion Vs Loops

Question

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?

--

Francis

Answer 1

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.

Horacehoracio

That an interesting (and correct I believe) way of putting it. +1 – Spindle

except when the built-in stack overflows. Then the iterative version will work while the recursive one crashes. – Beira

@mmr: Well, it's easier to change the size of a user-defined stack than the built-in thread stack in a multi-component environment (where your stack size change may interfere with other components). And recursion usually stores a little bit more data on the stack (return address as well as local state). But in general both scale the same in terms of stack usage. Algorithms without backtracking can be coded iteratively with no stack or using tail-recursion, both are O(1). With backtracking, big-O will be the same for both as well. – Horacehoracio

that's the theory. Now try recursively walking through each element in 1024x1024x512 piece of volumetric data and watch your stack explode. – Beira

It's the amount of state that has to be maintained for backtracking that controls the stack usage. No backtracking? Tail recursion -> no stack growth. Lots of state? The iterative case will be needing gigabytes of memory as well. – Horacehoracio

Answer 2

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.

Alkylation

In theory, all recursive solutions can be rewritten iteratively. In practice, you end up creating and maintaining a stack frame for a lot of them. – Essentialism

can we always be sure? I am trying to search for a more formal proof, but no success so far... It will be really helpful to know when we should be trying hard to find a solution, vs when we should not... – Francis

@sachin: You can be sure because all recursion is iterative, it just involves overhead in maintaining state information (i.e. the stack). – Scup

Answer 3

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.

Puke

Answer 4

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.

Scup

Answer 5

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.

Spindle

Not true. Ordinary while loop can continue without known end. In fact, quicksort can be written in iterative form,where recursion is replaced by stack. – Parallax

Answer 6

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:

http://www.texttoolkit.com/index.php?option=com_content&view=article&catid=35%3Atechnology&id=60%3Abeyond-recursive-descent&Itemid=55

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.

Vigil