Naive recursive fib(4): which calls repeat, and what does that tell you?
Tap to flip
Back
fib(2) is computed twice and fib(1) three times. The subproblems overlap, so memoization or bottom-up dynamic programming turns the exponential running time into O(n).