Understanding $O(2^n)$ time complexity due to recursive functions
If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.