Какова пространственная сложность рекурсивного алгоритма Фибоначчи без учета стековых вызовов?

Question

Если мы не учитываем память вызовов стека, то какое место занимает рекурсивное фибноначи?

Я читаю это здесь , и оно говорит 0 (N), но я перепутано, следует ли нам включать стековую память или нет при рассмотрении пространства.

Псевдокод:

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

Answer 1

без учета памяти вызовов стека. Это снова O (n), потому что вы передаете переменную, копия которой создается в новом вызове функции, и это происходит n раз в n функциях, поскольку максимальная высота дерева рекурсии в любое время n или максимальный уровень равен n + 1, поэтому асимптотически мы можем сказать, что это O (n).

В случае подхода снизу вверх мы снова используем массив для хранения прошлого значения, чтобы он также стал пробелом O (n) (но умным способом мы можем применить подход снизу вверх для работы только с 3 переменными, которые может рассматриваться как O (1) пространство).