A recursive function calls itself. That’s a strange and beautiful concept, one that saves a lot of coding time, but how does it really work?

Before I get into the traditional factorial recursion example, the following code demonstrates a simple and visual example of recursion.

#include <stdio.h>

int recurse(int v)
{
    printf("v = %d\n",v);
    if( v == 5 )
        return(v);
    recurse(v+1);
}

int main()
{
    int a = 0;

    recurse(a);

    return(0);
}

If you build this code, you may see a -Wreturn-type compiler warning. The code is fine, despite the warning.

In this code, recurse() is a recursive function. It calls itself at Line 8:

recurse(v+1);

That statement is legal, and it works. No limitation exists on a function calling itself, but the code must have a way to escape. That escape valve is provided at Line 6 with an if statement. All the calls to recurse() at Line 8 are unwound by the return at Line 7.

Here’s a sample run:

v = 0
v = 1
v = 2
v = 3
v = 4
v = 5

So v keeps increasing because recurse() keeps calling itself. Then when v is equal to 5, the return statement kicks in and the whole thing unwinds. It’s a rather convoluted way to increment a variable 5 times, and nothing is really done with that variable, but the function is recursive.

Now if it didn’t work, then the code would run amok. With recurse() continually calling itself, eventually the stack pointer, which keeps track of function calls in C, would exceed its allocated memory. To see that disaster in action, comment out Lines 6 and 7 in the code so that the recurse() function looks like this:

int recurse(int v)
{
    printf("v = %d\n",v);
//  if( v == 5 )
//      return(v);
    recurse(v+1);
}

Build and run again.

On my computer, I saw the following:

...
v = 262000
v = 262001
v = 262002
v = 262003
v = 262004
v = 262005
Segmentation fault: 11

After calling itself 262,005 times, the recurse() function finally blew the stack. That’s the situation you want to avoid.

In next week’s Lesson, I’ll show how a factorial calculation can be done by using recursion.