You've just identified the problem: overlapping subproblems cause exponential slowdown. And the solution is dynamic programming (DP (dynamic programming))! I'll show you two approaches:
memoization (top-down) adds a cache (a place to store results) to your recursive code, storing results as you compute them.
Tabulation (bottom-up) builds an array iteratively (using a loop instead of recursion), filling it from base cases upward. Both give you time instead of . Next, I'll walk you through both approaches and show you how to speed up your Fibonacci solution.