algorithmpro
Recursion: the Fibonacci call tree
Two recursive calls per step grow a tree of calls, and expose a lot of repeated work.
- time
- O(2ⁿ)
- space
- O(n)
// step through it
step 1 / 13
1function fib(n) {2 if (n <= 1) return n;3 return fib(n - 1) + fib(n - 2);4}- calls
- = 1
- fib(4)
Call fib(4). It needs fib(3) and fib(2) first.
// pro lesson
Unlock the full walkthrough
This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.
See pricingHow it works
fib(n) calls fib(n − 1) and fib(n − 2), so the calls branch into a tree. Each call waits until both children return, then adds their results. Look closely and the same subproblems appear again and again: fib(2) is computed twice even for n = 4, and the tree roughly doubles with every extra n. That is O(2ⁿ) time. Dynamic programming fixes it by remembering answers.
Practice spotting this pattern →