Your naive Fibonacci runs in time and uses space. (Well, honestly not exactly this. But let's go with that for now) Why? Each call makes two more calls, creating a binary tree of depth .
That's roughly total calls. Try it: makes hundreds of calls, makes thousands, makes over a billion. Exponential growth is brutal. Adding just to almost doubles the work.
This is why finishes quickly but would take years. How do we fix this? Before you read the next unit, try to answer: what if you could remember answers you've already computed? How would that change things?