Fibonacci sequence implementation

Question

This was too slow for my computer:

int f(unsigned int x)
{
    if(x <= 1) return 1;
    else return f(x-1)+f(x-2);
}

/* main */
int main()
{ 
    for(int i = 0; i < 50; i++) cout << f(i) << endl;
    return 0;
} 

So I've made a faster implementation. It works, but is it well-written? Is there some way to improve it?

void f(unsigned long now)
{
    static int counter = 0;
    static unsigned long last = 0, tmp = last;
    if(counter++ == 50) 
    {
        last = tmp = counter = 0;
        return;
    }
    std::cout << last + now << std::endl;
    tmp = last;
    last = now;
    f(now+tmp);
}

// calling f(1); in main

Answer 1

There's a few things that could be improved about the new function:

• Most obviously, its interface is awkward: when you call f, you have to pass 1 and it prints the first 50 Fibonacci numbers. The old function was better in that respect: you call it with an argument n and get back the n'th Fibonacci number.

• It uses an iterative algorithm, implemented recursively using a tail call. That's common in functional languages, but I think in C++ a loop is simpler.

• It passes state from one invocation of the function to the next through static variables. That seems inelegant.

Here's a straightforward iterative implementation of the algorithm:

// return the n'th Fibonacci number
unsigned long fib(unsigned int n) {
    if (n == 0) return 0;
    unsigned long previous = 0;
    unsigned long current = 1;
    for (unsigned int i = 1; i < n; ++i) {
        unsigned long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

Answer 2

First of all: If you want execution speed, an iterative approach to fibonacci is faster. That said, implementing a recursive solution is a nice exercise.

Some other remarks:

1. Code that does something should not perform IO. Separate computations from UI. This will also allow you to output values only once, which is faster.
2. Your function is very specialized. What if I want to calculate only fib(5)? Or up o fib(65)? Strive to write reusable components.
3. Note that std::endl flushes the output buffer, which takes time. If you just want to output a newline, use std::cout << last + now << '\n'; instead.

4. Instead of

   static unsigned long last = 0, tmp = last;

   write

   static unsigned long last = 0, tmp = 0;

   It's clearer, and you won't have to change anything in case you remove last at some point.

5. I would pass state around, rather than use static variables.

Maybe something like this:

// Helper function
int fib_do(int max, int curr, int one_before, int two_before)
{
    if (curr == max-1) return one_before+two_before;

    return fib_do(max, curr+1, one_before+two_before, one_before);
}

int fib(int n)
{
    if (n <= 1) return 1;

    return fib_do(n, 1, 1, 0);
}

However, this snippet (and your second version) is basically just the iterative solution implemented using recursion.

Note that this snippet has not in any way been optimized for speed. However, it facilitates the Return Value Optimization.

Finally: Consider using some form of caching to increase the speed of your recursive function.