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 occasional appendices and optional examples in this module are for advanced material that you will not need for this module. They are intended for enthusiastic students who are interested in going further in programming for its own sake.

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.