Recursion exercises

Comments and questions to John Rowe.

Fibonacci number

For integer n > 0 the Fibonacci number F(n) is given by:

• F(0) = 0
• F(1) = 1
• For n > 1 F(n) = F(n-1) + F(n-2)

Write a recursive function that returns F(n). From within main() call it for n equals 0 to 40 and print out the result. Your output should start:

0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144

A problem

You will have noticed that towards the end the numbers got to be quite large and that your function got a bit slow. To show this even we will need to extend the precision of the function so change the type of your function from "int" to "long long":

long long yourfunctionname(int n) {

This is an eight-byte int and the format to print it out is "%lld". (That's three letters: El-El-Dee.)

Now extend your loop to go up to 80 and see what happens! The problem is that the number of calculations needed to calculate F(n) is approximately 2 * F(n), since each result is just the sum of ones and zeros.

Optional: better, real-life recursion

The answer is to cache our values: ie after calculating them store them for later use.

1. Within main() declare an long long array initialised to all zeros:

   	long long cache[MAX+1] = {0};
   

2. Have your Fibonacci function accept the array as an argument.
3. For n > 1 have your function check to see if cache[n-1] is zero. If it is call yourfunctionname(n-1), but if it is non-zero do not.
4. Do the same for n-2.
5. Have your function set cache[n] to be the correct expression using the values of the cached array not by calling your function again. (The aim is that your function should only ever be called once for a given value of n.) Now return cache[n].
6. Try running your loop both from zero to eighty and also backwards from eighty to zero. This will act as a good test of your caching code.