What is the space complexity of a recursive fibonacci algorithm?

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).