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.

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.

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.

Many thanks!

It seems unsigned long integer is limited to sequence #47. What data type should I use for sequence #50?

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.

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.

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?

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! :)

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.

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