Welcome to the Ranch
What have they told you about that recursive Fibonacci program? You realise that to work out fib(4) you call fib(2) and fib(3) and fib(3) calls fib(2), so you end up calling fib(2) twice. If you try fib(5), you call fib(3) twice and fib(2) thrice. It is a classic example of what can go wrong with recursion if you design it badly.
You can design Fibonacci programs where the number of recursive calls is proportional to the argument (so fib(12) would need 2 more calls than fib(10), but they are slightly more complicated. That is linear complexity
O(
n).
Kaldewaij shows a version of Fibonacci numbers where the number of calls is approximately proportional to the logarithm of
n:
O(log
n).
What you have there runs in exponential complexity, which you can verify by adding a counter to your fib method:
O(1.618ⁿ) approximately. 1.618 is the golden ratio.