What is the time complexity of recursion and the call stack?

Best case O(n) memoised. Worst case O(2ⁿ) naive. Space complexity is O(n) stack depth.

Recursion and the call stack

easy

Every call gets a stack frame holding its own state. See the frames pile up and unwind, count how many times fib(2) is recomputed, then switch the cache on and watch the tree collapse into a line.

Best O(n) memoisedWorst O(2ⁿ) naiveSpace O(n) stack depth

Loading the recursion and the call stack engine…

Where to go next

Towers of Hanoi

medium

Three lines of recursion, 2ⁿ − 1 provably optimal moves.

Coin change (DP)

medium

One subproblem per amount, and no first choice can trap it.

Merge sort

medium

Split to single elements, then merge back in order.