double foo(int n)
{
int i;
double sum;
if(n == 0)
{
return 1.0;
}
else
{
sum = 0.0;
for(i = 0; i < n; i++)
{
sum += foo(i);
}
return sum;
}
}
The space complexity of the above code is?
View worked solution
Answer: B
The space complexity of a recursive function is determined by the maximum depth of the recursion stack (i.e., the maximum number of active stack frames at any point during execution).
Let's analyze the execution of foo(n):
- When
foo(n)is called, it executes a loop fromi = 0ton - 1, making sequential recursive calls tofoo(i). - Because these calls are sequential, the space allocated for
foo(i)is deallocated (popped from the stack) as soon as it returns, before the next callfoo(i + 1)begins. - The maximum depth of the recursion stack occurs during the deepest chain of active recursive calls, which happens when the loop reaches its last iteration at each level:
At this peak, there are active stack frames on the call stack.
Since each stack frame requires a constant amount of memory, , to store local variables (i, sum) and the parameter n, the maximum space complexity is:
Hence, the correct option is B.
Free practice · Your answers on this page are not saved.