The same smaller problem is needed again and again by different branches of the recursion.

In naive Fibonacci, fib(30) is computed by both fib(32) and fib(31). Caching its result removes the repeated work.