Next: Towers of Hanoi. Up: Recursion. Previous: None.

Fibonacci numbers

Recursion is the concept of something being defined in terms of itself. It sounds like it's circular - but it's not necessarily so. A circular definition, like defining a rose as a rose, is termed infinite recursion. But some recursive definitions aren't circular: They have a base case, where the recursive definition no longer applies, and the definition for any other case eventually reaches the base case.

In mathematics, things are often defined recursively. For example, the Fibonacci numbers are often defined recursively. The Fibonacci numbers are defined as the sequence beginning with two 1's, and where each succeeding number in the sequence is the sum of the two preceeding numbers.

1 1 2 3 5 8 13 21 34 55 ...

We obtained 8 in the above sequence by summing the previous two numbers (3 and 5).

A formal mathematical definition would define this using mathematical symbols.

         1                if n = 0 or n = 1
F(n) = {
         F(n-1) + F(n-2)  otherwise

This makes the recursiveness of the definition obvious: Notice how we've defined F(n) in terms of F (namely, F(n-1) + F(n-2)). (Incidentally, such recursive definitions of functions are called recurrences.)

In computer programming, also, it's often convenient to define something recursively. And Java allows you to do this - all you have to do is to use the function within its own definition. The following program computes and prints a Fibonacci number requested by the user.

import csbsju.cs160.*;

public class Fibonacci {
    public static void main(String[] args) {
        IO.println("Which Fibonacci? ");
        IO.println("It is " + fib(IO.readInt()));
    }
    private static int fib(int n) {
        if(n <= 1) return 1;
        else return fib(n - 1) + fib(n - 2);
    }
}

Notice how the recursive function has its base case - in this example, the base case is when n is at most 1, when the program returns 1 without any further recursive calls. Recursive programs must always have a base case! Novices tend to forget to include a base case when programming.

As a programmer, it's important that you understand how this works within the computer. The computer will go through the following process to compute fib(3):

3 exceeds 1, so I need to compute and return fib(3 - 1) + fib(3 - 2).
To compute this, I first need to compute fib(2).
  2 exceeds 1, so I need to compute and return fib(2 - 1) + fib(2 - 2).
  To compute this, I first need to compute fib(1).
    1 is less than or equal to 1, so I need to return 1.
  Now that I know fib(1), I need to compute fib(0).
    0 is less than or equal to 1, so I need to return 1.
  I now know fib(2 - 1) + fib(2 - 2) = 1 + 1 = 2. I return this.
Now that I know fib(2) is 2, I need to compute fib(1).
  1 is less than or equal to 1, so I need to return 1.
I now know fib(3 - 1) + fib(3 - 2) = 2 + 1 = 3. I return this.

It helps to draw a recursion tree to illustrate the different recursive calls entered in the process of the computation. A recursion tree has a node for each call of the method, connected by a line to the method call that called it. For the example of fib(3), the recursion tree would be as follows.

For fib(5), the following is the recursion tree.

Next: Towers of Hanoi. Up: Recursion. Previous: None.