Recursion

Overview

We can define the factorial of a number as follows:

$x! = x \cdot (x - 1) \cdot (x -2) ... \cdot 2 \cdot 1$

If we want to write a Java method that computes the factorial of a number, we can do it with a loop like so:


public static int fact(int x) {
    int product = x;

    for (int i = x - 1; i >= 1; i--) {
        product *= i;
    }

    return product;
}

Alternatively we could define the factorial of a number recursively like so:

$x! = x \cdot (x - 1)!$

What "recursion" really means is that we define something in terms of itself. Here we say that the factorial of a number x is equal to x times the factorial of x - 1. If we use this definition for 5!, we would have:

$5!= 5 \cdot 4!$

Then replacing 4!, we get:

$5! = 5 \cdot 4 \cdot 3!$

If we keep going, we'll get:

$5! = 5 \cdot 4 \cdot 3 \cdot 2!$

Next, we have:

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1!$

If we keep expanding like this, however, we will never be able to stop:

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0 \cdot -1 \cdot -2 ...$

Which will give us zero.

Recursion like this can turn into a circular definition that is not helpful. For recursion to work and make sense, we have to specify when the recursion stops. In the factorial definition, we can say that the factorial of 0 is 1, and otherwise it's the recursive definition:

\[ x! = \begin{cases} 1, & \text{when } x = 0 \\ x \cdot (x - 1)!, & \text{otherwise} \\ \end{cases} \]

Now when we expand a factorial, we will stop at x = 0, and just use the value 1 instead of expanding on forever. Mathematicians frequently use recursive definitions like this.

We can use recursive definitions like this to write code as well. To do this, we just have a method that calls itself. Following is a factorial method based on the recursive definition:


public static int fact(int x) {
    if(x == 0) {
        return 1;
    } else {
        return x * fact(x - 1);
    }
}

Notice that the method calls itself — that's what makes it recursive.

How Recursion Works

If we call fact(4), then we will start to execute the fact method with 4 as a parameter. In doing so, we call fact(3) which then begins to execute. Then fact(2) gets called which calls fact(1) which calls fact(0).

fact(0) stops the recursion by just returning a value of 1 directly. Then the program goes back to where it left off in fact(1) and multiples 1 * 1 and returns 1. Then we are back where we left off in fact(2) which multiplies 2 by the result of fact(1) or 1 giving 2.

fact(2) then returns that 2 up to fact(3) which multiplies 3 by the 2 to get 6. The 6 is then returned up to fact(4) which multiplies 4 by the result of fact(3) or 6 giving 24. Then fact(4) returns to where it was called at with the final answer of 24.

This program can be found here: Fact.java

Infinite Recursion

If the factorial method forgets to check for the 0 value, and always calls itself like so:


int fact(int x) {
    return x * fact(x - 1);
}

Then we run into something called infinite recursion. Infinite recursion is like an infinite loop, except that it will eventually crash the program:

Exception in thread "main" java.lang.StackOverflowError
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
    // 1000 lines removed
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)
	at Fact.fact(Fact.java:9)

The stack trace consists of 1024 calls to this method before the virtual machine killed us. Recall that whenever a method is called, an stack frame is pushed onto the stack. The stack is only so big, so if we keep pushing stack frames over and over, without popping any, the stack will overflow.

Whenever writing a recursive program, it's important to make sure that there is always a "base case" that returns something directly. The recursive case should then move us closer to the base case so that the recursion will eventually stop. Following are some other examples of recursive method.