¿Qué es la recursividad de cola?
Mientras empezaba a aprender ceceo, me encontré con el término recursivo de cola . ¿Qué significa exactamente?
Considere una función simple que suma los primeros N números naturales. (p.ej sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).
Aquí hay una implementación simple de JavaScript que usa recursividad:
function recsum(x) {
if (x === 0) {
return 0;
} else {
return x + recsum(x - 1);
}
}
Si llamaste a recsum(5), esto es lo que evaluaría el intérprete de JavaScript:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
Observe cómo cada llamada recursiva debe completarse antes de que el intérprete de JavaScript comience a realizar el trabajo de calcular la suma.
Aquí hay una versión recursiva de cola de la misma función:
function tailrecsum(x, running_total = 0) {
if (x === 0) {
return running_total;
} else {
return tailrecsum(x - 1, running_total + x);
}
}
Aquí está la secuencia de eventos que ocurrirían si llamara a tailrecsum(5), (que efectivamente sería tailrecsum(5, 0), debido al segundo argumento predeterminado).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
En el caso recursivo de cola, con cada evaluación de la llamada recursiva, se running_totalactualiza.
Nota: La respuesta original utilizó ejemplos de Python. Estos se han cambiado a JavaScript, ya que los intérpretes de Python no admiten la optimización de llamadas finales . Sin embargo, si bien la optimización de llamadas finales es parte de la especificación ECMAScript 2015 , la mayoría de los intérpretes de JavaScript no la admiten .
En la recursividad tradicional , el modelo típico es que primero se realizan las llamadas recursivas y luego se toma el valor de retorno de la llamada recursiva y se calcula el resultado. De esta manera, no obtendrá el resultado de su cálculo hasta que haya regresado de cada llamada recursiva.
En la recursividad de cola , primero realiza sus cálculos y luego ejecuta la llamada recursiva, pasando los resultados de su paso actual al siguiente paso recursivo. Esto da como resultado que la última declaración tenga la forma de (return (recursive-function params)). Básicamente, el valor de retorno de cualquier paso recursivo determinado es el mismo que el valor de retorno de la siguiente llamada recursiva .
La consecuencia de esto es que una vez que esté listo para realizar el siguiente paso recursivo, ya no necesitará el marco de pila actual. Esto permite cierta optimización. De hecho, con un compilador escrito apropiadamente, nunca debería tener un desbordamiento de pila con una llamada recursiva de cola. Simplemente reutilice el marco de pila actual para el siguiente paso recursivo. Estoy bastante seguro de que Lisp hace esto.
Aug 29 '2008 03:08