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?

--

score 17 · Accepted Answer · answered Apr 17 '10 at 20:13

17

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.

answered Apr 17 '10 at 20:13

Ben Voigt

277,958
43
419
720

That an interesting (and correct I believe) way of putting it. +1 – Josh K Apr 17 '10 at 20:19
7

except when the built-in stack overflows. Then the iterative version will work while the recursive one crashes. – mmr Apr 17 '10 at 20:39
3

@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. – Ben Voigt Apr 17 '10 at 22:55
1

that's the theory. Now try recursively walking through each element in 1024x1024x512 piece of volumetric data and watch your stack explode. – mmr Apr 18 '10 at 01:57
1

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. – Ben Voigt Apr 18 '10 at 03:30

score 2 · Answer 2 · answered Apr 17 '10 at 20:12

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.

answered Apr 17 '10 at 20:12

Oded

489,969
99
883
1,009

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. – Chris Lutz Apr 17 '10 at 20:14
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... – sachin Apr 17 '10 at 20:16
1

@sachin: You can be sure because *all recursion is iterative*, it just involves overhead in maintaining state information (i.e. the stack). – Adam Robinson Apr 17 '10 at 20:19

score 1 · Answer 3 · edited May 23 '17 at 12:09

1

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.

edited May 23 '17 at 12:09

Community

1
1

answered Apr 17 '10 at 20:17

IVlad

43,099
13
111
179

score 1 · Answer 4 · answered Apr 17 '10 at 20:18

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.

score 0 · Answer 5 · answered Apr 17 '10 at 20:11

0

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.

answered Apr 17 '10 at 20:11

Josh K

28,364
20
86
132

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. – el.pescado - нет войне Apr 17 '10 at 20:27

score 0 · Answer 6 · answered Apr 17 '10 at 20:40

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.

Recursion Vs Loops

6 Answers6