Calculating the space complexity of a C-function?

Question

Consider the following C-function:

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 function is:

(a) O(1) (b) O(n) (c) O(n!) (d) O(n^n)

What I've done is calculating the recurrence relation for the above code but I'm still not able to solve that recurrence. I know this is not home work related site. But any help would be appreciated.

This is my recurrence.

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) +........+ T(1)+ S

Where S is some constant.

Answer 1

That would depend on whether you're talking about stack, or heap space complexity.

For the heap, it's O(1) or O(0) since you're using no heap memory. (aside from the basic system/program overhead)

For the stack, it's O(n). This is because the recursion gets up the N levels deep.

The deepest point is:

foo(n)
    foo(n - 1)
        foo(n - 2)

        ...

        foo(0)