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:
- 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.
- Your function is very specialized. What if I want to calculate only
fib(5)? Or up o
fib(65)? Strive to write reusable components.
- 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.
static unsigned long last = 0, tmp = last;
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.
- I would pass state around, rather than use
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.