Recursion

A recursive function is defined in terms of base cases and recursive steps.

• In a base case, we compute the result immediately given the inputs to the function call.

• In a recursive step, we compute the result with the help of one or more recursive calls to this same function, but with the inputs somehow reduced in size or complexity, closer to a base case.

Consider writing a function to compute factorial. We can define factorial in two different ways:

which leads to two different implementations:

Iterative

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

Recursive

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

In the recursive implementation on the right, the base case is n = 0, where we compute and return the result immediately: 0! is defined to be 1. The recursive step is n > 0, where we compute the result with the help of a recursive call to obtain (n-1)!, then complete the computation by multiplying by n.

To visualize the execution of a recursive function, it is helpful to diagram the call stack of currently-executing functions as the computation proceeds.

Let’s run the recursive implementation of factorial in a main method:

public static void main(String[] args) {
    long x = factorial(3);
}

At each step, with time moving left to right:

In the diagram, we can see how the stack grows as main calls factorial and factorial then calls itself, until factorial(0) does not make a recursive call. Then the call stack unwinds, each call to factorial returning its answer to the caller, until factorial(3) returns to main.

Another common example is the Fibonacci series:

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return 1; // base cases
    } else {
        return fibonacci(n-1) + fibonacci(n-2); // recursive step
    }
}

Fibonacci is interesting because it has multiple base cases: n=0 and n=1.

Notice that where factorial’s stack steadily grows to a maximum depth and then shrinks back to the answer, Fibonacci’s stack grows and shrinks repeatedly over the course of the computation. Here is another representation of recursive function calls, called a recursion tree: