Una pila es una generalización y hay muchas áreas de memoria en una computadora en funcionamiento que podrían llamarse “pilas”. Siempre y cuando los datos se lean en el orden opuesto al que se colocan, llamamos un área de memoria una “pila”.
Cuando hablamos de recursividad, estamos hablando de la “pila de ejecución” para un hilo específico en un proceso. El programador no crea esto, ya que el compilador crea el código para tratarlo. En tiempo de ejecución, cada subproceso de ejecución tiene una pila para que el código pueda realizar un seguimiento de dónde estaba antes y pueda restaurar ese estado anterior cuando se realiza con el actual. Mire este código, por ejemplo, prestando atención a los comentarios a la derecha.
función c (int z) {// 7. establezca z en 9, como se pasó en
devuelve z + 7; // 8. la pila de abajo se muestra en este punto
}
función b (int y) {// 4. establece y en 3, como se pasó en
int w = 6; // 5. establece w en 6
retorno c (y + w); // 6. guardar la ubicación de devolución, llamar a c (9)
}
función a () {// 1. comienza aquí
int x = 5; // 2. pon un 5 en la pila
imprimir (b (3) + 5); // 3. guardar la ubicación de devolución en la pila, llamar a b (3)
}
- Cómo realizar un recorrido de orden posterior en un árbol binario
- ¿Cuál es el programa de clasificación rápida que tiene su mediana como pivote?
- ¿Las estructuras en lenguaje C son similares a los objetos en Java?
- ¿Qué problema exacto está resolviendo el 'comercio conversacional'?
- ¿Cómo debo usar el libro Introducción a los algoritmos de Cormen de manera efectiva? ¿Es mejor elegir un tema que haya encontrado en algún lugar de la programación competitiva y leer un algoritmo relacionado con eso o revisarlo de principio a fin?
Aquí hemos llamado a la función a (), que llama a b (), que luego llama a c (), por lo que la pila de ejecución contendría tres cuadros, uno para c (), b () y a (). (Nota: en algunas computadoras la pila de ejecución crece hacia arriba y en otras crece hacia abajo, pero los resultados son los mismos).
7 // parte superior de la pila dentro de c (), se agregará un 7
9 // el valor de z en c (), pasado de b ()
volver a dentro de b // donde en el código debemos volver a
6 // el valor de w en b ()
3 // el valor de y en b ()
volver a dentro de // otro retorno a realizar, en un ()
5 // valor de x, dentro de a ()
La pila de ejecución crece a medida que realizamos llamadas a funciones / métodos anidados o recursivos, como puede ver en el ejemplo anterior.
Sin embargo, la mayoría de los compiladores realizan la Optimización de llamadas de cola. Si esto se compilara con TCO, los dos valores de la pila “return to b” y “6” nunca se pondrían en la pila. ¿Por qué? Debido a que el compilador se daría cuenta de que, después de llamar y devolver c (), no quedaría nada que hacer en b (), y que la variable w ya no se usaría. Entonces, el optimizador del compilador crearía código que nunca pondría esas dos cosas innecesarias en la pila de ejecución en primer lugar. c () volvería directamente dentro de a () y todo seguiría funcionando como se esperaba.
Entonces, si su código está escrito de tal manera que no hay nada más que hacer después de una llamada anidada / recursiva, y si el optimizador del compilador admite TCO, entonces la recursión no hace que la pila crezca sin límites, ni afecta negativamente el rendimiento. Pero solo si”.
Para responder a su pregunta a un nivel más básico: El programador no necesita estar consciente de que se está utilizando una pila cuando escribe funciones recursivas. Pero deben tener en cuenta que el código compilado será más eficiente si la llamada recursiva es lo último en la función, y si no se debe hacer nada más con el valor que devuelve la llamada, aparte de devolverlo intacto.
PD: en caso de que le interese, esta es una buena coyuntura para explicar la gran diferencia en la ejecución entre funciones convencionales y lambdas. Las variables (x, y, z) en los ejemplos anteriores, como puede ver, se guardan en la pila. Si estos se escribieran como lambdas, entonces estos “datos de la pila” se almacenarían en el espacio de datos (el montón) en lugar de la pila.
- Para lambdas, las variables / parámetros locales se almacenan en una estructura de datos junto con un puntero / referencia al punto de entrada del código de función. La lambda es simplemente un puntero / referencia a esa estructura. Esto significa que la lambda continúa existiendo después de que el código ha regresado.
- Para funciones / métodos convencionales, las variables / parámetros se almacenan directamente en la pila junto con las direcciones de retorno. Esto significa que las variables / parámetros se sacan de la pila cuando la función regresa.
