69. How do you analyse the space complexity of a recursive algorithm?
MediumAlgorithm analysis
Show model answer
Count the maximum depth of the call stack times the space per frame, plus any heap memory allocated. Only the frames on the current path are alive at once, so a recursion tree with exponentially many nodes can still use small space. Naive Fibonacci makes Θ(φ^n) calls but its maximum depth is n, so it uses O(n) stack.
Examples: recursive binary search uses O(log n) stack (O(1) iteratively), merge sort uses O(log n) stack plus O(n) for the merge buffer, and quicksort uses O(log n) expected stack but O(n) in the worst case unless you recurse on the smaller side first and loop on the larger. Languages without tail-call optimisation (JavaScript in most engines, Python) need care with deep recursion on large inputs.