FIBONACCI NUMBERS

In this lab, you will see an example of a horribly slow recursive method. The problem is not with recursion itself but with with a poor design. A better design yields a recursive version that is just as fast as the iterative version.

FIBONACCI NUMBERS

The arrangement of scales on pine cones, the florets of daisies and the family tree of male bees all share a common feature: they exhibit the Fibonacci sequence. This sequence is named after a 13th century Italian mathematician who discovered the sequence : 1, 1, 2, 3, 5, 8, 13, 21, ... . Each of the first two terms is 1. After that, each term is the sum of the preceding two terms (for example, 8 = 5 + 3). This definition immediately leads to the following recursive method:

/**
 *  Returns the nth Fibonacci number.
 *
 *  @param n - the integer whose Fibonacci number is sought.
 *
 *  @throws IllegalArgumentException - if n is less than or equal to 0.
 *
 */
public static long fib (int n)  
{
  if (n <= 0)
     throw new IllegalArgumentException();
  if (n <= 2 )
    return 1;
  else 
    return fib (n - 1) + fib (n - 2); 
} // method fib

Here is a step-by-step, execution-frame trace of this method when the initial call is:

fib (5)

The return statement in the else part has two recursive calls. To clarify what is going on, a check mark is placed above a recursive call rather than in front of the return statement.

___________________________________________________

Step 0:

___________________________________________________

Step 1:

___________________________________________________

Step 2:

___________________________________________________

Step 3:

___________________________________________________

Step 4:

___________________________________________________

Step 5:

___________________________________________________

Step 6:

___________________________________________________

Step 7:

___________________________________________________

Step 8:

___________________________________________________

Step 9:

___________________________________________________

Step 10:

___________________________________________________

Step 11:

___________________________________________________

Step 12:

___________________________________________________

Step 13:

___________________________________________________

Step 14:

___________________________________________________

Step 15:

___________________________________________________

Step 16:

___________________________________________________

The above trace illustrates the redundancy of calculations for this definition of the method fib: fib (3) is calculated in steps 1 through 6 and again in steps 10 through 15.