It’s truly a scary thing: A function calls itself. This trick can be done without damage to the space-time continuum, and nothing explodes when it’s done correctly.

It’s a programming feature called recursion. Rather than avoid it, or just stand confused, you may discover that recursion comes in handy.

As an example of recursion, I’ve been working on a text-mode version of the popular Minesweeper game, shown in Figure 1.

Figure 1. My text-mode Minesweeper game.

As with the Windows version, when you “click” on an empty cell, the game reveals all other empty cells adjacent. It keeps doing that, until you have the large empty field, shown in Figure 1.

The function that reveals the empty squares is recursive, i.e., it calls itself. That recursion saved a lot of redundant programming: If the cell adjacent is empty, then the same function is called again to hunt down more empty cells.

As with all recursion, eventually an end condition appears. In my minesweeper game, a non-empty cell is found. At that point, all the recursive function calls “unwind,” and control is returned from the recursive function.

Another example of recursion might be a function to traverse a maze: Every time an intersection is encountered, the function is called to turn in a certain direction. Eventually the maze is traversed, the end is reached, and the function unwinds. That’s a simple explanation.

Recursion can often be easier to understand than it is to code. In a way, it’s like a loop in that recursion must feature an ending scenario. Without it, the recursion keeps winding tighter and tighter util the program crashes.

The standard, “I’m completely not creative” programming example for recursion is to calculate a factorial value.

Way back when you were sleeping through math, you missed the bit on factorials: It’s where you have an expression like 5!, which translates into 5×4×3×2×1. That’s the factorial of 5, which calculates to 120.

Whatever.

In C, you could code a factorial by using a simple loop, as shown here:

#include <stdio.h>

int main()
{
    long a,f,x;

    printf("Enter an integer: ");
    scanf("%ld",&f);
    a = f;
    for(x=f-1;x>0;x--)
        a *= x;
    printf("%ld! = %ld\n",f,a);

    return(0);
}

The code fetches input from the user, storing an integer value in variable f. A loop counts down from f-1 to 1. Each iteration, the value of variable a is multiplied by the countdown value. In effect, you get f! = f × (f-1) × (f-2) × (f-3) . . .× 1.

Sample run:

Enter an integer: 18
18! = 6402373705728000

The code works for small values, but when the numbers get bigger, the size of the long int variable overflows and the results are incorrect. But you get the point: The code calculates a factorial.

To do the same thing with recursion, you need a factorial function. I’ll explore that function in a future Lesson. For next week’s Lesson, I’ll show a simple and hopefully clear example of recursion.