Overlapping subproblems
Overlapping subproblems happen when a task can be divided into subproblems that are reused multiple times. A pure recursive solution often ends up solving the same subproblems over and over, wasting work.
Example: the Fibonacci numbers. To compute F(n), you calculate F(n-1) and F(n-2). But to get F(n-1), you also need F(n-2). So F(n-2) gets computed more than once, showing overlapping subproblems.
Because of this repetition, a naive recursive Fibonacci calculation is slow and grows exponentially as n increases.
If a problem also has optimal substructure, dynamic programming can help by saving the results of subproblems and reusing them.
Two implementations:
- fibonacci: uses regular recursion without saving results, so it repeats work.
- fibonacci_mem: uses memoization (caching) to store each F(k) once and reuse it whenever needed.
The memoized version is much faster, especially for larger n, since it avoids repeated work and grows more like linear time rather than exponential.
This page was last edited on 3 February 2026, at 08:02 (CET).