4.6. Marcos de pila: Implementación de la recursividad¶
Supongamos que en lugar de concatenar el resultado de la llamada recursiva a aCadena con la cadena de cadenaConversion, modificamos nuestro algoritmo para incluir las cadenas en una pila antes de hacer la llamada recursiva. El código de este algoritmo modificado se muestra en el ActiveCode 1.
Cada vez que hacemos una llamada a aCadena, incluimos un carácter en la pila. Volviendo al ejemplo anterior podemos ver que después de la cuarta llamada a aCadena la pila se vería como muestra la Figura 5. Tenga en cuenta que ahora podemos simplemente extraer los caracteres de la pila y concatenarlos en el resultado final, "1010".
Figura 5: Cadenas colocadas en la pila durante la conversión¶
Figura 5: Cadenas colocadas en la pila durante la conversión
El ejemplo anterior nos da una idea de cómo implementa Python una llamada a función recursiva. Cuando se llama a una función en Python, se asigna un marco de pila para manejar las variables locales de la función. Cuando la función realiza la devolución, el valor devuelto se deja en el tope de la pila para que la función invocante tenga acceso a él. La Figura 6 ilustra la pila de llamadas después de la instrucción return de la línea 4.
Figura 6: Pila de llamadas generada por aCadena(10,2)¶
Figura 6: Pila de llamadas generada por aCadena(10,2)
Note que la llamada a aCadena(2//2,2) deja como valor devuelto un "1" en la pila. Este valor devuelto se utiliza entonces en lugar de la llamada de función (aCadena(1,2)) en la expresión "1" + cadenaConversión[2%2], que dejará la cadena "10" en el tope de la pila. De esta manera, la pila de llamadas de Python reemplaza la pila que usamos explícitamente en el Programa 4. En nuestro ejemplo de sumatoria de números en una lista, usted puede pensar en el valor devuelto en la pila como una sustitución de una variable de acumulación.
Los marcos de pila también proporcionan un entorno para las variables utilizadas por la función. A pesar de que estamos llamando a la misma función una y otra vez, cada llamada crea un nuevo entorno para las variables que son locales a la función.