2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I just noticed that if I call this function again it will print numbers until the program crashes. Do I have to set the static variables back to zero? \$\endgroup\$ – Normal People Scare Me Jul 10 '13 at 21:00
  • \$\begingroup\$ I can't say I'm too good with recursion, but this link may help you with the algorithm. \$\endgroup\$ – Jamal Jul 10 '13 at 21:08
  • 1
    \$\begingroup\$ You do need to reset the static variables. They will retain their value across multiple function calls. \$\endgroup\$ – user27155 Jul 10 '13 at 21:18
  • 1
    \$\begingroup\$ Your new code does something completely different. I would try making incremental changes. This doesn’t mean that you cannot redesign the code (you should!) but you should clarify upfront what the semantics of the code are actually supposed to be. A personal preference: don’t reimplement the function iteratively – stick with the recursive solution but try to make it more efficient. Hint: in order to achieve this you cannot return a single int, you need to return a pair of ints. \$\endgroup\$ – Konrad Rudolph Jul 10 '13 at 22:53
  • 1
    \$\begingroup\$ @NormalPeopleScareMe: That should work. You can also use std::uint64_t from the cstdint library. \$\endgroup\$ – Jamal Jul 11 '13 at 16:32
3
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ “If you want execution speed, an iterative approach to fibonacci is faster” – If you make such claims, please back them up with evidence. I claim that a non-naive recursive implementation is on par with an explicit loop. \$\endgroup\$ – Konrad Rudolph Jul 11 '13 at 8:43
  • 3
    \$\begingroup\$ Iterative solution is faster. Try to calculate the 1000000000 Fibonacci number :) \$\endgroup\$ – cat_baxter Jul 11 '13 at 11:25
  • \$\begingroup\$ +1 Interesting approach (in relation to recursion). I also would've preferred the last and tmp on separate lines, but that's just a minor thing. \$\endgroup\$ – Jamal Jul 11 '13 at 12:16
  • \$\begingroup\$ @cat_baxter: a tail recursive function compiled with a compiler that has in effect tail recursion optimization does not use any more stack than whatever stack was allocated for its initial invocation (ignoring whatever stack is used by methods the function itself invokes) and effectively should compile to a loop in whatever "lower level" language it is compiling to. That link, though interesting, is not exactly relevant. \$\endgroup\$ – JayC Jul 11 '13 at 23:29
  • \$\begingroup\$ @cat_baxter: ...well, relevant to whether or not a tail recursive function is faster than an iterative approac, I should say. \$\endgroup\$ – JayC Jul 11 '13 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.