Fibonacci: the recursion tree repeats work; memoisation removes it
This animation draws the full recursion tree for fib(5), showing all 15 calls and highlighting the repeated subtrees that cause exponential growth (roughly 1.6^n calls). It then rebuilds the same computation using a memo table, marking each unique subproblem once so only n calls are needed. The side-by-side view makes visible why caching results turns wasteful recursive branching into linear-time dynamic programming, useful for students learning algorithm efficiency and recursion.
16:9 · Preview before teaching · automatic layout checks do not establish subject accuracy
The prompt that made it
The recursion tree for fib(5) with the repeated subtrees highlighted (15 calls, about 1.6^n in general), then a memo table that stores each answer once so the work becomes n calls; dynamic programming.
Make the next one in this series
- Show the same comparison for fib(10) to see the gap between exponential and linear growth widen
- Animate converting the memoized recursion into a bottom-up iterative table-filling algorithm
- Visualize time complexity growth curves for exponential, linear, and logarithmic algorithms on one graph
