What is the space complexity of a recursive fibonacci algorithm without considering stack calls?

Question

If we don't consider stack call memory, then what is the space consumed by the recursive fibnonacci?

I read it here and it says 0(N) but I am confused whether we should include stack memory or not while considering the space.

The pseudocode:

int Fibonacci(int n)
{
   if ( n == 0 )
      return 0;
   else if ( n == 1 )
      return 1;
   else
      return ( Fibonacci(n-1) + Fibonacci(n-2) );
}

Which recursive Fibonacci algorithm? There are at least two that I know of, likely there are more. — VLAZ, Mar 20 '20 at 06:32
https://forgetcode.com/c/188-fibonacci-series-using-recursion — Sahil Sharma, Mar 20 '20 at 07:12
You should include this in the question. Even as a pseudo code. — VLAZ, Mar 20 '20 at 07:13
If you consider stack-memory depends on you. I would say of cause memory used on a stack is also used memory, so why shouldn't i be counted. — MrSmith42, Mar 20 '20 at 07:28

mss · Answer 1 · 2020-03-20T10:39:54.533

without considering stack call memory, It is again O(n) because you are passing a variable whose copy gets created in new function call, and this happens n times in n functions as maximum height of the recursion tree at any time is n or maximum level is n + 1 so asymptotically we can say it is O(n).

In case of bottom up approach again we use array to store the past value so that also becomes O(n) space(but in a clever way, we can make bottom up approach to work with only 3 variables which can be considered as O(1) space).

What is the space complexity of a recursive fibonacci algorithm without considering stack calls?

1 Answers1