Please wait
Loading technology simulations
The requested content is still loading.
Finished experimenting?
Save one completion to this browser's signed guest ledger, or directly to your account when signed in.
Please wait
Loading technology simulations
The requested content is still loading.
Save one completion to this browser's signed guest ledger, or directly to your account when signed in.
| n | naive | memo |
|---|---|---|
| 5 | 15 | 9 |
| 20 | 21,891 | 39 |
| 30 | 2,692,537 | 59 |
1fib(n):2 if n ≤ 1: return n3 return fib(n−1) + fib(n−2)
This recursion tree simulator animates how fib(n) is computed, so overlapping subproblems stop being abstract. In naive mode each call spawns two children and the tree grows like the golden ratio to the n, recomputing fib(2) hundreds of times. Toggle Memoized and the same tree collapses to a thin left spine with cache-hit stubs — each subproblem computed once. The lab's signature interaction: click any circle to highlight every other node that recomputes that same value, with a live count, so wasted work is impossible to miss. A calls-to-solve card compares naive versus memoized at n = 20 and n = 30 (millions of calls versus dozens), and a synced pseudocode panel highlights the base case, recursive step, or cache hit as the tree builds.
recursion tree · fibonacci algorithm · memoization · dynamic programming · overlapping subproblems · exponential vs linear time · top-down DP
Browse all Technology simulations →
Free to use in your browser — no signup required. Found a bug or have an idea to make it better? Tell us.