13. Recursion

We have seen many functions that call other functions, e.g. unit test functions for validating the output of other functions. Recursion in computer science refers to a function that calls itself.

One place where recursion appears naturally is in mathematical functions defined by recursive formulas.

For example, the factorial function

\[ n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 \]

can be defined by the recursive formula \[ n! = n \cdot (n-1)! \]

In code, this would be

    factorial(n) = n * factorial(n-1)

Note that the value of factorial(n) depends on the value of factorial(n-1).

However, there is an important danger to be aware of when implementing a recursive function. The programmer must ensure that the recursion will stop at some point. Every function call uses computer memory (on the ‘stack’), so an infinite recursion will cause the program to run out of memory (called a ‘stack overflow’).

In order to ensure that the recursion stops, one option is to define a base case (usually \(n = 0\)):

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

Another option is to define a maximum recursion depth.

In spite of this danger, recursion can be useful in cases where the calculated values of a function are saved (‘cached’) for use in the future. For example, recursion can be used to calculate binomial coefficients, and all intermediate calculations could be saved for future function calls (e.g. in a 2D array). More details about the recursive calculation of binomial coefficients can be found in the exercises.