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.