Recursion: a Function that Calls Itself

Dr. Lawlor, CS 202, CS, UAF

Here's a totally ordinary for loop:

	for (int i=0;i<10;++i) {
		cout<<"I'm at iteration "<<i<<"\n";
	}

(Try this in NetRun now!)

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:

	int i=0;
start:
	if (i<10) {
		cout<<"I'm at goto "<<i<<"\n";
		++i;
		goto start;
	}

(Try this in NetRun now!)

"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:

void loopfn(int i) { // Recursive "loop"
	if (i<10) {
		cout<<"I'm at recursion "<<i<<"\n";
		loopfn(++i);
	}
}

(Try this in NetRun now!)

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.

Transforming Iteration into Recursion

In general, you can take any for loop and transform it into a recursive function call. For example:

	for (VAR X=V; TEST; INCREMENT) BODY;

Can be rewritten as a function "loopy(V)":

void loopy(VAR X) {
	if (TEST) {
		BODY;
		loopy(INCREMENT);
	}
}

If you've got other variables that you modify inside the loop body, you need to pass them down into each call:

void loopier(VAR X,BODYVARS &B) {
	if (TEST) {
		BODY;
		loopier(INCREMENT,B);
	}
}

So we can see that iteration can always be transformed, in a straightforward way, into recursion.

Dangers of Recursion

Quick, what's wrong with this code?

void recursive(int i) { // Recursive "loop"
	if (i<10) {
		cout<<"I'm at recursion "<<i<<"\n";
		recursive(i);
	}
}

(Try this in NetRun now!)

It's an easy mistake to make! Now how about this code?

void recursive(int i) { // Recursive "loop"
	cout<<"I'm not messing that up again!  i = "<<i<<"\n";
	recursive(++i);
}

(Try this in NetRun now!)

D'oh! In general, it's easy to leave out some crucial step in recursion, because you ALWAYS need:

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.

The other danger of recursion is that you end up using too much space. For example, I can easily iterate to 20 million:

int foo(void) {
	enum {n=20000000};
	int sum=0;
	for (int i=0;i<n;i++) sum+=i;
	return sum;
}

(Try this in NetRun now!)

But this recursive version crashes!

enum {n=20000000};
void recursive(int i) { // Recursive "loop"
	if (i<n) {
		recursive(++i);
	}
}

(Try this in NetRun now!)

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.

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.

Transforming Recursion into Iteration

There are times when you want to get rid of recursion, for example because it uses too much stack space, or because your machine doesn't even support recursion (pre-2010 graphics cards don't do recursion, and neither do some tiny embedded computers).

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) {
	if (i<1) return 0; // base case
	else {
		return i+sumrecurse(i-1);
	}
}

int foo(void) {
	return sumrecurse(10);
}

(Try this in NetRun now!)

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.

int tailrecurse(int i,int sum) {
	if (i<1) return sum; // base case
	else {
		sum+=i;
		return tailrecurse(i-1,sum);
	}
}

int foo(void) {
	return tailrecurse(10,0);
}

(Try this in NetRun now!)

This is identical to the following loop, which could then be further transformed into a typical "for" loop.

int foo(void) { // iterative version
	int i=10, sum=0;
	while (true) {
		if (i<1) break; // base case
		else {
			sum+=i;
			--i;
		}
	}
	return sum;
}

(Try this in NetRun now!)

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

int fibonacci(int n) {
	if (n<2) return 1; // base case
	else return fibonacci(n-1)+fibonacci(n-2); // recursion
}

int foo(void) {
	return fibonacci(10);
}

(Try this in NetRun now!)

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:

	enum {m=10};
	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];

(Try this in NetRun now!)

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.

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!