Complexidade espacial da função recursiva
Dada a função abaixo:
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
Eu sei que a complexidade do tempo do Big O éO(2^N), porque cada chamada chama a função duas vezes.
O que não entendo é por que a complexidade do espaço / memória éO(N)?