递归算法空间复杂度面试释义：栈帧数还是变量占用空间？
Great question—this is a super common point of confusion, especially since recursive algorithms have a unique memory overhead that non-recursive ones don’t. Let’s break down how this is typically interpreted in interviews, and whether you need to split definitions:
1. What Interviewers Usually Mean First
When an interviewer asks about the space complexity of a recursive algorithm, their initial focus is almost always on the maximum depth of the call stack (i.e., the maximum number of active stack frames at any point during execution).
This is because recursive calls rely on the program’s call stack to store state (return addresses, local variables, parameters) for each pending function invocation. For example:
- A recursive factorial function for
n=5will have a call stack depth of 5 (factorial(5) → factorial(4) → ... → factorial(1)), so the call stack contributes O(n) space. - This is the "recursive-specific" overhead that interviewers care most about, since it’s the primary reason recursive solutions can hit stack overflow errors for large inputs.
2. The Full Picture: Call Stack + Local Variables
Strictly speaking, space complexity measures the total maximum memory used by the algorithm at any single point in time. That means you do need to account for both:
- The call stack’s stack frames (each holding parameters, return addresses, and local scalars)
- Any additional data structures or variables created within the function (like a local array, hash map, or large object)
For example, if your recursive function creates a size-k array every time it’s called, and the call stack depth is n, the total space complexity would be O(n * k) — because at the peak of execution, there are n active stack frames, each with their own size-k array.
In interviews, if your recursive solution uses significant auxiliary space beyond the call stack, you should explicitly mention both components (e.g., "The call stack contributes O(n) space, and the local hash map adds O(k) space, so total space complexity is O(n + k)").
3. How This Differs from Non-Recursive Algorithms
Non-recursive algorithms don’t have the call stack overhead from nested function invocations (the only stack frames are from the main function or top-level calls, which aren’t counted as part of the algorithm’s space complexity). So their space complexity focuses solely on auxiliary data structures or variables created by the algorithm itself.
Recursive algorithms don’t require separate definitions—instead, you just need to explicitly include the call stack space as part of your calculation, since it’s a core part of how the algorithm runs.
内容的提问来源于stack exchange，提问作者user1008636
