Here's a totally ordinary for loop:

for (int i=0;i<10;++i) {It's actually pretty easy to re-write the loop in terms of "goto" statements. You have to do this transformation in primitive environments like assembly language:

cout<<"I'm at iteration "<<i<<"\n";

}

int i=0;"Recursion" is when a function calls itself. Here's a recursive implementation of the same loop. You have to start with a call to "loopfn(0);" to set up i with the right starting value:

start:

if (i<10) {

cout<<"I'm at goto "<<i<<"\n";

++i;

goto start;

}

void loopfn(int i) { // Recursive "loop"The basic deal here is "loopfn" calls itself with different parameters. Those different parameters cause "loopfn" to do different things. Eventually, the calls stop (the "if" fails), and all those nested function calls return. This is recursion.

if (i<10) {

cout<<"I'm at recursion "<<i<<"\n";

loopfn(++i);

}

}

for (VAR X=V; TEST; INCREMENT) BODY;Can be rewritten as a function "loopy(V)":

void loopy(VAR X) {If you've got other variables that you modify inside the loop body, you need to pass them down into each call:

if (TEST) {

BODY;

loopy(INCREMENT);

}

}

void loopier(VAR X,BODYVARS &B) {So we can see that iteration can always be transformed, in a straightforward way, into recursion.

if (TEST) {

BODY;

loopier(INCREMENT,B);

}

}

void recursive(int i) { // Recursive "loop"It's an easy mistake to make! Now how about this code?

if (i<10) {

cout<<"I'm at recursion "<<i<<"\n";

recursive(i);

}

}

void recursive(int i) { // Recursive "loop"D'oh! In general, it's easy to leave out some crucial step in recursion, because you ALWAYS need:

cout<<"I'm not messing that up again! i = "<<i<<"\n";

recursive(++i);

}

- A "base case", where the recursion will stop. This is almost always some kind of "if" statement.
- An increment, so you're recursing on different values.

int foo(void) {But this recursive version crashes!

enum {n=20000000};

int sum=0;

for (int i=0;i<n;i++) sum+=i;

return sum;

}

enum {n=20000000};The problem is the recursive version runs out of "stack space" where local variables from called functions get stored, because each call to recursive makes a new copy of 'i'. This is a bigger problem on 32-bit machines, which only have a few gigabytes of address space total, and may devote as little as a few megs of that for stack space.

void recursive(int i) { // Recursive "loop"

if (i<n) {

recursive(++i);

}

}

Running out of stack space during a deep recursive call is a common problem, and a tough one to track down--the compiler-generated code that accesses stack variables will crash, despite the fact that everything about those variables looks perfectly fine! The solution is to decrease the recursion depth, or eliminate recursion entirely.

Some simple recursive calls can be almost trivially transformed back into iteration. For example, the cases above are quite easy to transform back to for loops.

Here's one that's not quite so obvious:

int sumrecurse(int i) {There's a particular style of recursion called a "tail recursion" that is designed to be easy to transform into a while loop. A tail recursive function doesn't touch the return value from the recursive call, so you drag along the modified value as a parameter.

if (i<1) return 0; // base case

else {

return i+sumrecurse(i-1);

}

}

int foo(void) {

return sumrecurse(10);

}

int tailrecurse(int i,int sum) {This is identical to the following loop, which could then be further transformed into a typical "for" loop.

if (i<1) return sum; // base case

else {

sum+=i;

return tailrecurse(i-1,sum);

}

}

int foo(void) {

return tailrecurse(10,0);

}

int foo(void) { // iterative version

int i=10, sum=0;

while (true) {

if (i<1) break; // base case

else {

sum+=i;

--i;

}

}

return sum;

}

But how could you remove the recursion from this Fibonacci program?

int fibonacci(int n) {The basic problem here is that to figure out fibonacci(10), I need not only fibonacci(9) like in an "i--" for loop, I also need fibonacci(8). There are a couple of ways to fix this, such as faking your own stack. But there's also a very beautiful technique called "dynamic programming", which is based on filling out a table of values:

if (n<2) return 1; // base case

else return fibonacci(n-1)+fibonacci(n-2); // recursion

}

int foo(void) {

return fibonacci(10);

}

enum {m=10};Note how the core of the for loop is actually the old body of the recursive function. As a bonus, the dynamic programming implementation is MUCH faster than the recursive version, because the recursive version re-calculates intermediate values many times, but the dynamic programming version does it only once.

int fibonacci[m+1];

for (int n=0;n<=m;n++)

{

int v=0;

if (n<2) v=1; // base case

else v=fibonacci[n-1]+fibonacci[n-2]; // read old values

fibonacci[n]=v; // write new value

}

return fibonacci[m];

In general, it's trivial to transform iteration into recursion; my languages teacher Gul Agha used to say "Iteration is just a degenerate form of recursion." But it can be hard to transform recursion into iteration. This means recursion is a more powerful technique than iteration, which is why many smart mathematically oriented programmers prefer it. But unlike goto, recursion's power is rarely overused; if anything, recursion is weird and scary enough that it's probably underused!