It’s the example of recursion most often used, but it’s not the best example. Of course, to illustrate a better example you need to approach concepts such as fractals and graphical programming doodads. My favorite form of recursion is traversing a directory tree. Regardless, the code for a factorial recursion remains the go-to workhorse.

As a reminder, a factorial is a mathematical calculation expressed as n!, which I pronounce, “N-bang.” Mathematicians would say, “N factorial,” but they’re not C programmers.

The calculation for n! is n × n-1 × n-2 × n-3 . . . n×1.

In an earlier Lesson, I showed how this calculation could be coded by using a loop. Below you see an example of coding a factorial by using recursion, i.e., a function that calls itself.

#include <stdio.h>

long factorial(long f);

int main()
{
    long a,b;

    printf("Enter an integer: ");
    scanf("%ld",&a);
    b = factorial(a);
    printf("%ld! = %ld\n",a,b);

    return(0);
}

long factorial(long f)
{
    if(f == 1)
        return(f);
    else
        return(f*factorial(f-1));
}

The factorial() function calls itself at Line 22, which is also where the factorial calculation is made:

f*factorial(f-1);

The insane part of this process is that the function calls itself in the return statement, which is typical of many recursive functions.

In the C language, what goes into the parentheses happens first, so before anything is returned, the function calls itself with a decremented value of variable f.

The effect is that f slides from its initial value down to 1, which is caught at Line 19. Then the value 1 is returned at Line 20.

Where is it returned to?

The value is returned to Line 22, where it’s multiplied by the previous value of f, or f+1. So the recursive calculation happens as the function unwinds, and it’s done backwards: f × f+1 × f+2 × f+3 . . . × f. That value keeps returning until it’s finally returned from the function.

That’s one recursive way to do a factorial. Other examples of recursion pop up in programming all the time, although it’s not as popular of a technique as working a loop.

I admit that recursion isn’t the easiest thing to comprehend. In a future Lesson, I’ll explore traversing a directory tree by using recursion. That’s the example I coded that best taught me how recursion works.