Skip to interview prep
Apexed

69. How do you analyse the space complexity of a recursive algorithm?

MediumAlgorithm analysis

Technical
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.

How do you analyse the space complexity of a recursive algorithm — Data structures & algorithms interview question — Apexed