Thread: Recursive Fibonacci function

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    135

    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.

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Oct 2010
    Posts
    135
    Many thanks!

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

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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.

  6. #6
    Registered User
    Join Date
    Oct 2010
    Posts
    135
    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.

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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?

  8. #8
    Registered User
    Join Date
    Oct 2010
    Posts
    135
    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!
    Last edited by 843; 03-18-2011 at 01:15 PM.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    Last edited by anon; 03-18-2011 at 02:09 PM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  2. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  3. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM