Recursion

As in most programming languages, functions in C can be recursive: a function can call itself. One of the most popular examples of a recursive function is factorial:

n! = 1 × 2 × ... × (n - 1) × n

For example, 5! = 1 × 2 × 3 × 4 × 5 = 120. We define that 0! = 1.

We can notice that n! = n × (n - 1)!, that is, 5! = 5 × 4!. This observation allows us to implement the factorial with recursion:

#include <stdio.h>

int factorial(int n) {
  if (n == 0) {
    return 1;
  }
	return n * factorial(n - 1);
}

int main() {
	int x = 5;
	printf("%d! = %d\n", x, factorial(x));
}

Of course it's possible to implement factorial using a simple for loop. I suggest that you do it for practice!

Let's look at this recursive implementation of the factorial function:

int factorial(int n) {
  if (n == 0) {
    return 1;
  }
	return n * factorial(n - 1);
}

Each recursive function must define a base case: a condition which makes the recursion stop. In our example, it's n == 0: if it's true, we immediately return 1 and exit the function. For all other values of n, we call the same function for n - 1. Assuming that n is not negative, the function will eventually exit.

Before we go further, let's talk about functions in general. Let's imagine two functions, f and g:

#include <stdio.h>

void f() {
  printf("f begin\n");
  g();
  printf("f end\n");
}

void g() {
  printf("g\n");
}

int main() {
  f();
  return 0;
}

The program starts executing main() and calls f(). The instructions of the program are executed sequentially, and if the execution jumps into function f(), it needs to know to which instruction it must return when f() completes. This information is stored in the memory; one function invocation creates one stack frame, which stores the return address, parameters, and local variables defined in the function being executed.

When f() starts, it first prints f begin\n, and then executes g(), at which point one more stack frame is created and the return address–the location in f() right after the call to g()–is stored there. Whenever g() finishes, the stack frame will be deleted, and the execution will go back to f() to its second printf. After f() finishes, the execution goes back to main().

The main point here is this: function invocation is not free, it consumes some memory. For regular functions, we don't care since this limit is high; but for recursive functions, it's very easy to make the program fail after consuming all available memory for storing stack frames.

This happens, for example, if a recursive function does not reach its base case. For example, what will happen if someone calls factorial(-1)? Try it out above and see how it fails! Do you understand why that happens?

Another problem with our factorial function is that it won't return the right value for big n. Actually, the last n it returns the correct result for is 12: 12! = 479001600. For 13!, the answer is wrong; this is not a problem with the recursion, but with the limits of the int type, which will will discuss separately.

Of course, there is not much use of such a trivial recursive function as the factorial. Soon we'll look at some more complex examples.