Project Euler 2 - Fibonacci sequence
The recursive definition of Fibonacci is an elegant one, but in practice it's something you would never want to use. Let's say you want to get fibonacci(5). How often does fibonacci get called?

fibonacci(5)
 =    fibonacci(4) + fibonacci(3)
 =   (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
 =   ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0)))
   + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))
 =   (((fibonacci(1) + fibonacci(0)) + fibonacci(1)) 
        + (fibonacci(1) + fibonacci(0))
     )
   + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))


That seems a lot for 0 + 1 + 1 + 2 + 3 + 5. Indeed, the recursive variant without memoization has exponential runtime. You have several options to reduce the time:


use an iterative variant (which leads to \$ \mathcal O(n)\$ instead of \$ \mathcal O(2^n)\$ per call of fibonacci),
use memoization (which, if done correctly, leads to \$ \mathcal O(n)\$ in worst case and \$ \mathcal O(1)\$ if the number was already calculated).


But that begs the question: do we actually need fibonacci? For a programming challenge, it's enough to calculate the sum in main, while you're calculating the numbers iteratively. If you're looking for performance, that would be the fastest variant (that doesn't use the closed form).