1. Introduction
2. Recursion
3. Cases
4. Further Examples
5. Checkpoint 1
6. Why Recursion?
7. Extra parameters
8. Checkpoint 2
9. Reflection

Cases

The idea of recursion is simple: a method completes a small portion of a problem, and calls itself to complete the remainder of the problem. Eventually, we peel off enough of the problem that we cannot peel off anymore -- the answer to our problem is trivial enough that the method doesn't need to call itself. The solutions are then fused together.

Accordingly, recursive methods typically include a conditional statement that checks to see if the remainder of the problem is trivial to solve. If so, we execute what's called the base case. If the problem is not trivial, then we execute the recursive case which includes a call to the method itself.

Note that a recursive method may have several base cases or several general cases. The Fibonacci sequence from lab 3, for example, can be recursively defined and has two base cases and one general case. Recall that the sequence starts out 0, 1, 1, 2, 3, 5, 8, 13, ..., where each number (other than the first and second) is the sum of the two numbers before it. In particular, suppose we have a function fib that given a number n, returns the n^th number of the Fibonacci sequence:

The complete Java code for computing the nth Fibonacci number looks like the definition above:

  /**
   * Recursively computes the nth Fibonacci number.
   */
  public static int fib(int n)
  {
    if (n == 0 || n == 1)
    {
      // base cases: return n
      return n;
    }
    else
    {
      // recursive case: sum of previous two values
      return fib(n - 1) + fib(n - 2);
    }
  }

Infinite recursion

If your method never stops calling itself, the Java virtual machine will soon run out of memory for creating new records on the call stack, and you normally end up throwing a StackOverflowError.