Complejidad espacial de la función recursiva
Dada la función a continuación:
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
Sé que la complejidad del tiempo Big O esO(2^N), porque cada llamada llama a la función dos veces.
Lo que no entiendo es por qué la complejidad del espacio / memoria esO(N)?