Count how many calls the recursive fibonacci(n) makes for n = 5, 10, 15, 20. What do you notice?

The counts are $15$, $177$, $1973$ and $21\,891$.

When $n$ grows by 5, the number of calls grows about eleven times. The function works out the same small values again and again. For $n = 40$, it would need hundreds of millions of calls.

A loop that keeps the last two numbers needs only $n$ steps. (Programmers also use a trick called memoisation: remember the answers that are already worked out.)