I just took a look at the output of gcc on -O1,-O2,-O3,and -Os (using the -S flag to output assembler.) It appears that with -O1 or -Os enabled, gcc turns the double recursion into single recursion. This makes the algorithm scale O(n) instead of O(fib(n)); i.e. much much faster. (Weirdly, -O2 and -O3 look to be double-recursing, but I didn't check closely. May be that gcc's smarter than me.)

It _also_ notices you're not using the result of fibonacci(40) and that it's a pure function, so it skips it. If you look at any optimized main function it's pretty much "set return code to 0 and get out of here."

To avoid this problem I've changed main to "return fibonacci(40)".

Now optimization becomes interesting. At -O3 main becomes 4 calls to fib(36), fib(35), fib(38), and fib(37). Crazy huh? It looks like it's unrolled fib(40) a few steps! At -Os I lost track of what's going on, but it starts with a call to fib(38) too. -O1 plays it pretty straight, and is what I'd recommend looking at for readable assembly.

-O2 and -O3 are easily the fastest. Something very clever is going on there.

    real	0m0.075s
    user	0m0.073s
    sys	0m0.001s

Moral of the story? Use -S! :)