Espacio Auxiliar con Funciones Recursivas

Requisito previo: la memoria de recursividad
utilizada por un programa a veces es tan importante como el tiempo de ejecución, especialmente en entornos restringidos, como los dispositivos móviles. 
Por ejemplo, si necesitamos crear una array de tamaño n, requerirá espacio O(n). Si necesitamos una array bidimensional de tamaño nxn, requerirá O(n ² ). 
El espacio de pila en llamadas recursivas también cuenta como espacio adicional requerido por un programa. 
Por ejemplo : 
 

int sum(int n)
{
   if (n <= 0)
       return 0;
   return n + sum(n-1);
}

static int sum(int n)
{
   if (n <= 0)
       return 0;
   return n + sum(n - 1);
}
 
// This code is contributed by Pratham76

def sum(n):
    if (n <= 0):
        return 0;
    return n + sum(n - 1);
 
 
# This code is contributed by Rajput-Ji

static int sum(int n)
{
   if (n <= 0)
       return 0;
   return n + sum(n - 1);
}
 
// This code is contributed by rutvik_56

<script>
 
function sum(n)
{
   if (n <= 0)
       return 0;
   return n + sum(n - 1);
}
 
</script>

En la función de ejemplo anterior, cada llamada agrega un nuevo nivel a la pila. 
 

     Sum(5)
    ->sum(4)
            ->sum(3)
            ->sum(2)
                ->sum(1)
                       ->sum(0)

Cada una de estas llamadas se agrega a la pila de llamadas y ocupa memoria real. Entonces, un código como este tomaría O (n) tiempo y O (n) espacio auxiliar. 
Sin embargo, el hecho de que tenga n llamadas en total no significa que ocupe O (n) espacio. Considere las siguientes funciones, que agregan elementos adyacentes entre 0 y n: 
Ejemplo: 
 

// A non-recursive code that makes n calls
// but takes O(1) extra space.
int pairSumSequence(int n)
{
    int sum = 0;
    for (int i=0; i<n; i++)
        sum += pairSum(i, i+1);
    return sum;
}
 
int pairSum(int a, int b)
{
    return a + b ;
}

En este ejemplo, habrá aproximadamente O(n) llamadas a pairSum. Sin embargo, esas llamadas no existen simultáneamente en la pila de llamadas, por lo que solo necesitamos espacio O(1). 
Este artículo es una contribución de Ranju Kumari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.