# Recursive Fibonacci function

• 03-18-2011
843
Recursive Fibonacci function
I'm supposed to write a recursive Fibonacci function which produces the nth sequence, and here's what I came up with:

Code:

```unsigned long int f(int x) {     int i;     //a, b, c are sequences 1, 2, 3 respectively     int a = 0, b = 1, c = 0;     if (x == 0) //sequence 0         return 0;     else if (x == 1) //sequence 1         return 1;     else {         //loop for sequence shifts         for(i = 2; i <= x; i++) {         c = a + b; //adds previous two sequences         a = b; //moves sequence 0 to 1         b = c; //moves sequence 1 to 2         }         return c;     } }```
Unless I'm misunderstanding the question, a recursive function is one that calls itself, and I'm having trouble implementing such a function into the above code. Basically, if I call the function sequentially, it works perfectly, but if I skip a number, the program crashes since it can't store the previous calculations correctly.
• 03-18-2011
whiteflags
The recursive fibonacci function does not use loops at all. Looking at the sequence in mathematical terms should be a pretty big hint what a recursive version looks like.
• 03-18-2011
anon
The definition of the sequence is:
fibo(0) = 0,
fibo(1) = 1,
fibo(n) = fibo(n - 1) + fibo(n - 2) where n > 1

That is also basically the recursive function for you ;).

Delete the loop and do the recursion.
• 03-18-2011
843
Many thanks!

It seems unsigned long integer is limited to sequence #47. What data type should I use for sequence #50?
• 03-18-2011
cyberfish
You can use an 64-bit type (unsigned long long int), but if you are dealing with numbers this large, you really should be using a bignum library.
• 03-18-2011
843
Will it work on my 32-bit CPU? I tried but it took forever to calculate. I closed the console after a minute.

Regarding bignum, I can't find any documentation about it.
• 03-18-2011
cyberfish
Yes it will. If there's no hardware support the compiler will generate code to do software emulation (which is a little slower).

It takes forever because the time required grows exponentially with this algorithm.

The recursive solution is actually a very inefficient solution to calculate Fibonacci sequence. It's only used as an example because it's simple.

Can you think of a faster solution?
• 03-18-2011
843
I think Core i5 should work, but I'm not sure about Windows 7 32-bit. Anyway, the faster way is obviously the original code I posted where each variables are simply shifted, rather than performing the calculations over and over.

EDIT: It took 5 minutes but it worked! Thanks a bunch! :)
• 03-18-2011
anon
The number of calls with the recursive function grows really fast. (I may be mistaken, but the number of times the recursive calls happens might be equal to the result you get!)

To make it usable in practice, you'd have to use memoization. The result of call with a particular value should be stored in some kind of look-up table, and only be computed if the result is not available.

Compare the running time of those two calls:
Code:

```#include <iostream> #include <cassert> const unsigned max_fibo = 100; unsigned long long fibo(unsigned n) {     if (n < 2) return n;     return fibo(n-1) + fibo(n - 2); } unsigned long long fibo(unsigned n, unsigned long long (&cache)[max_fibo]) {     assert(n < max_fibo);     if (n < 2) return n;     if (cache[n] == 0) {         unsigned long long result = fibo(n-1, cache) + fibo(n - 2, cache);         cache[n] = result;         return result;     }     return cache[n]; } int main() {     unsigned value = 45;     unsigned long long fibo_table[max_fibo] = {};     std::cerr << fibo(value) << '\n';     std::cerr << fibo(value, fibo_table) << '\n'; }```
It may look complicated, but it means if your program needs more than one fibonacci number, subsequent calls already have the table filled in.

Counted the number of recursive calls with the simple version. For fibo(n), there's fibo(n + 1) - 1 function calls.