Familiarize yourself with the Fibonacci numbers.

The Fibonacci sequence is a sequence of numbers determined by the following rule:

• The first two numbers in the sequence are 1 and 1.
• All other numbers in the sequence are the sum of the preceding two.
For example, the third Fibonacci number is 1 + 1 = 2, the fourth number is 1 + 2 = 3, and the fifth is 2 + 3 = 5. If f_n denotes the nth Fibonacci number, then
• f_n = 1 if n is 1 or 2
• f_n = f_n-1 + f_n-2 if n > 2
What are the sixth, seventh, and eighth Fibonacci numbers?

Write a recursive function to compute the nth Fibonacci number.

Copy the files

• fibonacci.h
• main.cpp
from the folder \\Dragon\cls_mcdowell\CS 420\fibonacci\ and the files
• ccc_time.h
• ccc_time.cpp
from the folder \\Dragon\cls_mcdowell\CS 420\CCCfiles\.

The file fibonacci.h contains the declaration int fibonacci(int n) for the function, and the file main.cpp contains a program to test it. The program reports how much time the fibonacci function takes, so you will also need the files ccc_time.h and ccc_time.cpp. Write the fibonacci function in a file fibonacci.cpp. Compile and test the program using the following values for n:

n		fn
10		55
20		6,765
30		832,040
40		102,334,155

When you have a correct (and documented!) version, print out your fibonacci.cpp to hand in.

Explore the efficiency of your Fibonacci function.

Your function probably took longer than you expected to compute the 40th Fibonacci number. To demonstrate how slow your function is, we'll do a race between you and your program. Get out a pencil or pen and a piece of scratch paper. Also pull out a hand calculator, or use the one on the computer (from the Start menu, choose Programs, then Accessories, then Calculator). Run your program, and enter 46 for n. While it is running, calculate and write down the first 46 numbers in the Fibonacci sequence.

You should be able to win this race, or at least come reasonably close. This is rather surprising, since a computer can clearly add and store numbers much more quickly than we can (even if we use a calculator). Let's add some output statements to the fibonacci function to figure out what's going on. Add the directive #include<iostream.h> to the file fibonacci.cpp. At the beginning of the function, add the statements

int answer;
cout << "Entering fibonacci: n = " << n << "\n";

Modify your function to store its return value in the variable answer instead of returning it, and then add the statements

cout << "Exiting fibonacci: n = " << n
     << " return value = " << answer << "\n";
return answer;

to the end of the function. These changes will cause a line to be printed at the beginning and end of every call to the fibonacci function. Compile and run the program and enter 5 for n. Notice that fibonacci(3) is called twice and fibonacci(2) is called three times. If we look carefully, we see that fibonacci(5) calls fibonacci(4) and fibonacci(3). But fibonacci(4) also calls fibonacci(3). That is why fibonacci(3) is called twice. The two calls to fibonacci(3) and the call to fibonacci(4) each call If we run the program and enter 6 for n, how many times will fibonacci(2) be called? (The output will run off the screen if you try this, but you should be able to figure out the answer just by thinking about it.) Write your answer and an explanation of why it is correct on the back of your print-out of fibonacci.cpp.

Try out a more efficient implementation.

To compute the Fibonacci numbers efficiently, we have to remove this duplication of work. As n gets large, the amount of duplication increases dramatically. To remove the duplication, we imitate what you probably did in computing the sequence by hand: keep track of the previous and current numbers in the sequence in order to calculate the next. To do this, we define an auxiliary function fib_helper

int fib_helper(int prev, int curr, int count, int n)
{
if (count == n)
   return curr;
else
   return fib_helper(curr, curr+prev, count + 1, n);
}

Let's look at how this function works. The first two parameters, prev and curr, represent the previous and current Fibonacci numbers. The parameter count represents how many of the Fibonacci numbers we've calculated (i.e. if count is 9, curr is the 9th Fibonacci number). The parameter n represents the index of the Fibonacci number we want (i.e. if n is 46, we want the 46th Fibonacci number). If count is equal to n, then curr is the number we want. Otherwise compute the next Fibonacci number by adding curr and prev and pass that along to the recursive call to fib_helper.

So to compute the nth Fibonacci number, we just have to start fib_helper off right:

int fibonacci(int n)
{
   if (n <= 2)
      return 1;
   else
      return fib_helper(1, 1, 2, n);
}

If n is 1 or 2, we can just return 1. Otherwise we call fib_helper with the first two Fibonacci numbers and let it calculate the rest.

The file \\Dragon\cls_mcdowell\CS 420\fibonacci\fibonacci2.cpp contains the definitions of these two functions. Remove your fibonacci.cpp from your CodeWarrior project (highlight it in the project window and then choose Remove Selected Items from the Project menu). Then add a copy of fibonacci2.cpp in its place. Compile and run the new program, entering 46 for n. What a difference! Unfortunately we have had to sacrifice the clarity of our program to gain efficiency. It should be pretty clear that your original function correctly computes the nth Fibonacci number. In contrast, this improved version requires some careful thought. When faced with a choice between clarity and efficiency, we need to think carefully about whether the gain in efficiency is worth the loss of clarity. Often it is not, but in this case the original program is impractical and the efficiency gain is so dramatic that it clearly pays off.

When you are done, turn in your print-out of fibonacci.cpp with your answer to the question from the third part of the lab.

If you have extra time, you can start work on the programming project (due next week at the beginning of lab).