Try using compiler optimisations...
fib|⇒ gcc -O4 fib.c -o fib fib|⇒ time ./fib ./fib 0.65s user 0.01s system 100% cpu 0.657 total fib|⇒ gcc -O3 fib.c -o fib fib|⇒ time ./fib ./fib 0.66s user 0.00s system 100% cpu 0.657 total fib|⇒ gcc -O2 fib.c -o fib fib|⇒ time ./fib ./fib 1.54s user 0.00s system 100% cpu 1.535 total fib|⇒ gcc -O1 fib.c -o fib fib|⇒ time ./fib ./fib 0.00s user 0.00s system 0% cpu 0.001 total
For some reason, it hates the O1 flag. Printing the result brings it close to the result without the optimization.
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