Space complexity in memoized fibonacci code

Question

void allFib(int n) {
   int[] memo = new int[n + 1];
   for(int i = 0; i < n; i++){
      System.out.println(i + ": "+ fib(i, memo));
   }
}

int fib(int n, int[] memo) {
   if (n <= 0) return 0;
   else if (n == 1) return 1;
   else if (memo[n] > 0) return memo[n];
   memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
   return memo[n];
}

In the above memoized code to print the first n fibonacci numbers, what is the space complexity due to the recursive calls in the fib method (memo[n]= fib(n - 1, memo) + fib(n - 2, memo);)? Even though they look like recursive calls, all they really do is lookup memo[n - 1] and memo[n - 2] as those are guaranteed to have already been computed. But because they are in this form and set up their own stack in memory, should each of those calls have a memory footprint? If so, what?

If I were to replace that line with memo[n] = memo[n - 1] + memo[n - 2], the space complexity contributed by THIS line would be reduced to O(1) right?

I know that the overall space complexity is at least O(n) because of the memo array of size n + 1.

Answer 1

The extra space complexity is O(1) even with recursive calls when you compute sequential Fibonacci numbers from the smallest to the largest one.

Indeed, each new call to fib in the loop results in exactly two calls (well, except for i = 0 and i = 1, where no additional calls are made). Each call requires a constant amount of space. The depth of recursion is bounded by 2, so the total extra amount of space required is constant.

If you replaced it with a loop with summation memo[n] = memo[n - 1] + memo[n - 2], the extra space complexity would stay O(1), so it would not be reduced.