Scientific Programming II

Programming in Java

Recursion Tutorial

Recursion is the act of calling a method in which it is defined. Most programming languages offer recursion (including Java); a special kind of language, functional languages, use recursion instead of loops like for and while. Recursion is one of the most powerful tools in a programmer's arsenal of CS kung fu, but can easily be misused: recursion increases how abstract (or in the CS world, meta) your program logic becomes.

Java is primarily object-oriented, however, the other primary paradigm supported is imperative programming. If you've programmed in C, you know all about imperative programming. Most often, a loop will be the first thing you'd consider to use in Java. However, recursion is available, and may even shorten your code by a considerable margin.

Let's look at a small recursive method:

public void printHello(int count)
{
    if (count == 0) return; // Base Case
    else {
        System.out.println("Hello!");
        printHello(count - 1); // Recursive call
    }
}

This function illustrates the best practice for a recursive method:

  1. There is one final base case that ends the method.
  2. Other cases call the method recursively, somehow updating the arguments
  3. There are no infinite cycles (i.e., the method will reach the base case)

Since this is a void method (ergo, nothing to return), we can refactor this method to use an implicit base case. Note, however, that while we save some LOC (lines of code), it is slightly less verbose and would require more documentation.

public void printHello(int count)
{
    if (count > 0) {
        System.out.println("Hello!");
        printHello(count - 1);
    }
}

In practice, while I normally choose brevity over verbosity, with recursion I always use verbosity over brevity. This does mean more typing, but will help you understand your code much better.

Now, let's look at a different recursive method, this one to compute factorials:

public int factorial(int num)
{
    int result;

    if (num == 0 || num == 1) return 1;
    else {
        result = factorial(num - 1) * num;
        return result
    }
}

Imagine now that we call this using factorial(4). Let's see how the function runs:

There is another (in my opinion better) way of writing the factorial function. It is based on a functional style of programming, where you avoid the use of mutable variables (or, in other words, 99% of Java variable usage).

public int factorial(int num)
{
    return factHelper(num, 1);
}

private int factHelper(int num, int acc)
{
    if (num == 0 || num == 1) return acc;
    else return factHelper(num - 1, acc * num);
}

At the expense of other private method, we avoid the use of the temporary variable result, and instead express our methods as computations on values. We accomplish this technique by making all of our temporary variables arguments to a helper method.

This will generally lead to cleaner looking code, and if you ever move to a functional language like Scala or F# you'll already start to feel at home.

Let's look at one final example, computing the nth Fibonacci number:

// Note, due to the limitations of int we can only compute
// up to the 49th number
public int fib(int num)
{
    return fibHelper(0, 1, num);
}

private int fibHelper(int a, int b, int num)
{
    if (num == 0) return a;
    else return fibHelper(b, a+b, num-1);
}

We all know the Fibonacci sequence is as follows:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Or, more functionally:

fib(n) = fib(n - 1) + fib(n - 2)

To see how we developed the recursive version, let's look at an imperative example:

public int fib(int num)
{
    int a = 0, b = 1;
    while (num > 0) {
        int tmpA = b;
        int tmpB = a+b;
        a = tmpA;
        b = tmpB;
        num--;
    }
    return a;
}

Holy code spaghetti Batman! That's a terrible looking method! Let's see the general steps how to transform this into a beautiful recursive method:

  1. Determine the base case
  2. Temporary variables will become arguments
  3. Loops will be converted into recursive helper methods
  4. Variable initialization should happen in the first method call

Well, in this case the base case (no pun intended) is what will make our while participle false, or when num == 0. Additionally, we have four temporary variables defined.

Lastly, we need to convert our while loop into a recursive method. We do this by combining our base case that we determined, and the temporary variables as arguments, into a new helper method. We can (and should!) use the same return statement from the imperative version.

private int fibHelper(int a, int b, int num)
{
    if (num == 0) return a;
    else {
        // Do the recursive call.
    }
}

Now, we know when we call the recursive method we have to update the arguments in such a way that the base case will always be reached. In this case, we only have to decrement num on each call. However, we see that in our imperative version we also update a and b. Therefore, we use these updates as the changes to the arguments a and b in our recursive call! So, finally, our helper method becomes:

private int fibHelper(int a, int b, int num)
{
    if (num == 0) return a;
    else return fibHelper(b, a+b, num-1);
}

Lastly, we know that initialization of temporary variables needs to happen during the first call of our recursive method. Therefore, we do so in our public method, leading to our original code:

public int fib(int num)
{
    return fibHelper(0, 1, num); // a = 0, b = 1
}

private int fibHelper(int a, int b, int num)
{
    if (num == 0) return a;
    else return fibHelper(b, a+b, num-1);
}