What is the space complexity of a naive recursive implementation of the Fibonacci sequence (without memoization), measured by the maximum depth of the call stack at any point during execution?

Although the naive recursive Fibonacci implementation performs an exponential number of total calls (O(2^n)) due to redundant recomputation, the call stack's maximum depth at any single point in time only grows linearly with n, since each recursive branch (following the fib(n-1) path) descends one level at a time down to the base case before any stack frames are popped. So the space complexity, governed by peak stack depth rather than total call count, is O(n). The O(2^n) figure in option E actually describes the time complexity (total node count in the recursion tree), not the space complexity, which is a common point of confusion.