LeetCode 509 Fibonacci - Problem Statement

Fibonacci sequence is an ideal example for recursion. To find $fib(n)$, you just call $fib(n-1)$ and $fib(n-2)$ and add them.

What could be simpler? I'll show you why this "obvious" solution breaks down when $n$ grows big. For small $n$ like $10$, it finishes instantly. For $n = 40$, your computer struggles. For $n = 50$, it never finishes. This problem will teach you why you need dynamic programming.