Physics and Astronomy |
Back to top
On this page
Contents Recursion exercisesFibonacci numberFor integer n > 0 the Fibonacci number F(n) is given by:
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 problemYou 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 recursionThe 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.
|