What is the space complexity of a recursive fibona

Question

This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition)

int fibonacci(int i) {
       if(i == 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonaci(i-2);
}

After watching the video on the time complexity of this algorithm, Fibonacci Time Complexity, I now understand why this algorithm runs in O(2ⁿ). However I am struggling with analyzing the space complexity.

I looked online and had a question on this.

In this Quora thread, the author states that "In your case, you have n stack frames f(n), f(n-1), f(n-2), ..., f(1) and O(1)" . Wouldn't you have 2n stack frames? Say for f(n-2) One frame will be for the actual call f(n-2) but wouldn't there also be a call f(n-2) from f(n-1)?

Answer 1

Here's a hint. Modify your code with a print statement as in the example below:

int fibonacci(int i, int stack) {
    printf("Fib: %d, %d\n", i, stack);
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1, stack + 1) + fibonacci(i - 2, stack + 1);
}

Now execute this line in main:

Fibonacci(6,1);

What's the highest value for "stack" that is printed out. You'll see that it's "6". Try other values for "i" and you'll see that the "stack" value printed never rises above the original "i" value passed in.

Since Fib(i-1) gets evaluated completely before Fib(i-2), there will never be more than i levels of recursion.

Hence, O(N).

Answer 2

As I see it, the process would only descend one of the recursions at a time. The first (f(i-1)) will create N stack frames, the other (f(i-2)) will create N/2. So the largest is N. The other recursion branch would not use more space.

So I'd say the space complexity is N.

It is the fact that only one recursion is evaluated at a time that allows the f(i-2) to be ignored since it is smaller than the f(i-1) space.

Answer 3

If anyone else is still confused, be sure to check out this Youtube video that discusses the space complexity of generating the Fibonacci Sequence. Fibonacci Space Complexity

The presenter made it really clear why the space complexity was O(n), the height of the recursive tree is n.