Recursion

Recursion is the ability for a method to call itself. It can be a very powerful tool, if used correctly. If used incorrectly, it could prevent your programs from ever terminating.

Let's start with one of the classic recursively defined functions, the factorial, denoted $n!$, it is defined as the product of all natural numbers less than or equal to it. For example, $5! = 5\times4\times3\times2\times1 = 120$. By definition, $0! = 1$. The mathematical definition follows:

$\Large n! = \left\{ \begin{array}{ll} n\times(n-1)! & \quad n > 0 \\ 1 & \quad n = 0 \end{array} \right.$

Here is an example evaluation:

$\large 5! = 5\times(5-1)! = 5\times4! = 5\times4\times(4-1)! = 5\times4\times3! = \ldots$

$= \large 5\times4\times3\times2\times1\times0! = 5\times4\times3\times2\times1\times1 = 120$

Notice how $n!$ doesn't always call itself. $0!$ will return 1 without calling factorial again. Cases where a recursive function doesn't call itself are called base cases, and they are required if you don't want infinite recursion.

The following Java method implements the factorial function.

static long fact (long n) {
     if (n > 0) n * fact(n-1);
     return 1;
}

Notice how the second return statement doesn't have an if statement, unlike the mathematical definition. This is because Java return methods (i.e. all methods that aren't void) must end with a return statement that isn't nested in another statement in case none of the other return statements are called.

Keep in mind that a recursive function as simple as this can be rewritten with a for loop.

static long fact (long n) {
    int res = 1;
    for (int i = 1; i <= n; i++)
        res *= i;
    return res;
}

Here is another classic recursively defined function: fibonacci numbers.

$\large Fib(n) = \left\{ \begin{array}{ll} Fib(n-1) + Fib(n-2) & \quad n > 1 \\ n & \quad n \le 1 \end{array} \right.$

The sequence starts with $0, 1$ and every successive term is the sum of the previous two. It goes:

$\large 0,1,1,2,3,5,8,13,21,34,55,89,89,144,233,377,610,987,1597,2584,4181,6765, \ldots$

The Java code is as follows:

static long fib (long n) {
    if (n > 1) return fib(n-1) + fib(n-2);
    return n;
}

However, this is an example of the occasional dangers of recursion. Copy and paste the code into an IDE and try to print fib(50). You may be staring at a blank console window for a long time because to calculate fib(50) over a billion recursive calls must be made. Why? Each call to fib makes two other calls to fib, which each make two other calls to fib, and so on. The run time of this method grows exponentially as n increases, so at a point fibjust takes too long to evaluate recursively. A forloop, however, will generate fibonacci numbers rather quickly and should definitely be used instead of this recursive method.

In general, be wary of writing and using recursive methods that usually make two or more recursive calls because their run time is probably exponential.

The Uses of Recursion

The true usefulness of recursion is in more advanced algorithms such as quicksort, merge sort, depth-first search, and flood fill. These algorithms might be discussed later in this book, but feel free to look them up now if you are curious. The reason recursion is explained so early in this book is because it is taught in CS A and it is a rather easy and intuitive concept to grasp and use.