Ch 12 Lab: Recursion -- Fibonacci Numbers

Authors: Peter Yoon and Bronzell Dinkins
Trinity College, Hartford, CT

Objectives

The objectives of this lab are:

To motivate the uses of recursion
To compare recursion and iteration

Problem Statement

For centuries mathematicians have been fascinated by the sequence of Fibonacci numbers. The sequence begins with

   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

where each number beginning with 2 is the sum of the two immediately preceding numbers.

In this lab, we are interested in implementing methods to compute the n^th Fibonacci number both iteratively and recursively. You will be asked to write Java code to implement the methods and to answer a series of questions. Your answers to these questions should be submitted in a text file Answers.txt.

Part 1 - An Iterative Version Using Arrays

Create a Java application Fibonacci.java that defines the Fibonacci class. This class should define a static method fibIter1() which takes an integer n and returns the n^th Fibonacci number using an array of integers which stores the Fibonacci sequence. Hint: You will need to construct a loop to achieve this.
Now define another Java class FibonacciTest in FibonacciTest.java to test the method. Note that since fibIter1() is a static method, it can be called without instantiating an object. See a partial implementation of this class at FibonacciTest.java.
Using these two classes, determine the n^th Fibonacci number when n = 5, 10, 15, 20.
Question 1: How many times does the loop repeat in fibIter1 in order to compute the n^th Fibonacci number for different values of n above?

Part 2 - A More Efficient Iterative Version

Add a static method fibIter2() to the Fibonacci class, which takes an integer n and returns the n^th Fibonacci number without using an array. Hint: Use the definition of the Fibonacci sequence, that is, each Fibonacci number is the sum of two immediately preceding numbers. Thus, you only need to keep track of three numbers (See also Exercise 29 of Chapter 6). Using this method determine the n^th Fibonacci number when n = 5, 10, 15, 20.

Part 3 - A Recursive Version

The n^th Fibonacci number can be defined recursively as follows:

   fib(1) = 1,
   fib(2) = 1,
   fib(n) = fib(n-1) + fib(n-2)       // if n > 2

Add a static method fib() to Fibonacci class, which takes an integer n and returns the n^th Fibonacci number using the recursive definition given above.
Using this method determine the n^th Fibonacci number when n = 5, 10, 15, 20.
Question 2: How many recursive calls are required to compute the n^th Fibonacci number for different values of n above? This can be computed by adding a static variable that is simple statement that will print the value of n whenever the fib() method is called.
Question 3: Which version (iterative or recursive) is more efficient?

Optional Part

The Fibonacci sequence is closely related to an irrational number called the Golden Mean. As you generate the list of quotients of consecutive Fibonacci numbers, such as

   8/5, 13/8, 21/13, 34/21, ...

you get closer and closer to the Golden Mean, which is exactly (1 + Math.sqrt(5)) / 2 and approximately 1.618033989. Modify your code to verify this fact. This can be shown by computing relative errors of an approximation at each step with respect to the true value, i.e.

             | Approx. - TrueValue |
   RelErr = -------------------------
                    TrueValue

where Approx = 8/5, 13/8, ... and TrueValue = (1 + Math.sqrt(5)) / 2. You should be able to observe that the error diminishes as you continue generating Fibonacci numbers.

Hand in

The documentation requirements for this lab are the the same as in the previous labs. Submit final versions of your files with appropriate documentation: Fibonacci.java , FibonacciTest.java, and Answers.txt.