How recursive Fibonacci works
fib(n) returns n for 0 and 1, and otherwise returns fib(n − 1) + fib(n − 2). Each call has to wait for both of its children before it can add their answers, so the stack grows down the leftmost branch first, unwinds, and grows again into the right branch.
The Python example computes fib(6) = 8. That takes 25 calls, and fib(2) alone is computed five times — the repeated work that memoization and bottom-up dynamic programming remove.
What to watch for when it runs
- The call stack shows one frame per pending call, each with its own n.
- Return values travel back to the caller that asked for them.
- The execution count on the function’s first line shows how many calls were made in total.
Time and space complexity
- Time
- O(2ⁿ)
- Space
- O(n)
The number of calls grows like φⁿ (about 1.6ⁿ). Only one path from the root is on the stack at a time, so memory is proportional to n.