La recursión de cola es un caso especial de recursión , en el que cualquier llamada recursiva es la última operación antes de regresar de la función. [1] Este tipo de recursividad es notable porque puede ser fácilmente reemplazada por iteración mediante una reorganización correcta formal y garantizada del código de función. La optimización de recursión de cola al convertirla en iteración plana se implementa en muchos compiladores de optimización. En algunos lenguajes de programación funcionales, la especificación garantiza la optimización de recurrencia de cola obligatoria.
Un mecanismo típico para implementar una llamada de función se basa en almacenar la dirección de retorno, los parámetros y las variables locales de la función en la pila y se ve así:
Por lo tanto, con cada llamada de función recursiva, se crea un nuevo conjunto de sus parámetros y variables locales que, junto con la dirección de retorno, se colocan en la pila, lo que limita la profundidad máxima de recursión al tamaño de la pila. En lenguajes puramente funcionales o declarativos (como Prolog), donde la recursión es la única forma posible de organizar cálculos repetitivos, esta limitación se vuelve extremadamente significativa, ya que, de hecho, se convierte en un límite en el número de iteraciones en cualquier cálculo cíclico, por encima de que se producirá un desbordamiento de pila .
Es fácil ver que la necesidad de expandir la pila para llamadas recursivas está dictada por el requisito de restaurar el estado de la instancia de llamada de la función (es decir, sus parámetros, datos locales y dirección de retorno) después de regresar de la función recursiva. llamar. Pero si la llamada recursiva es la última operación antes de salir de la función de llamada y el resultado de la función de llamada debe ser el resultado de que devolverá la llamada recursiva, ya no importa guardar el contexto: ya no se usarán parámetros ni variables locales, y la dirección de retorno ya está en la pila. Por lo tanto, en tal situación, en lugar de una llamada de función recursiva completa, simplemente puede reemplazar los valores de los parámetros en la pila y transferir el control al punto de entrada. Siempre que la ejecución siga esta rama recursiva, se ejecutará, de hecho, el bucle habitual. Cuando finaliza la recursividad (es decir, la ejecución pasa a través de la rama terminal y llega al comando de retorno de la función), el retorno ocurrirá inmediatamente al punto de inicio desde donde se llamó a la función recursiva. Por lo tanto, a cualquier profundidad de recursividad, la pila no se desbordará.
La recursión de cola se usa a menudo en programas en lenguajes de programación funcionales . Es natural expresar muchos cálculos en dichos lenguajes en forma de funciones recursivas, y la capacidad del compilador para reemplazar automáticamente la repetición de cola con iteración significa que, en términos de eficiencia computacional, es igual al código equivalente escrito en forma iterativa. .
Los creadores del lenguaje funcional Scheme , uno de los dialectos de Lisp , apreciaron tanto la importancia de la recursión de cola que en la especificación del lenguaje ordenaron a cada compilador de este lenguaje que implementara la optimización de recursión de cola sin falta y describieron el conjunto exacto de condiciones que una función recursiva debe cumplir para que la recursividad sea optimizada en ella. [2]
Un ejemplo de una función recursiva para factorial usando recursividad de cola en los lenguajes de programación Scheme , C y Scala :
| Esquema | C | Scala |
|---|---|---|
| ( define ( factorial n ) ( define ( fac-veces n acc ) ( if ( = n 0 ) acc ( fac-veces ( - n 1 ) ( * acc n )))) ( fac-veces n 1 )) | int fac_times ( int n , int acc ) { devolver ( n == 0 ) ? cuenta : fac_times ( n - 1 , cuenta * n ); } int factorial ( int n ) { volver fac_times ( n , 1 ); } | @tailrec def factorial ( it : Int , resultado : Int = 1 ) : Int = { si ( eso < 1 ) resultado más factorial ( it - 1 , resultado * it ) } |
Cabe señalar que no todos los programas recursivos simples son recursivos de cola. El mecanismo de optimización de recurrencia de cola descrito anteriormente impone una serie de restricciones significativas en los programas a los que se puede aplicar, que los desarrolladores que confían en el uso de esta optimización deben tener en cuenta.
Como ejemplo de una función recursiva simple que no es recursiva de cola y no se puede convertir automáticamente en una función iterativa, esta es la forma recursiva más obvia de calcular factorial , que generalmente se da en los libros de texto como el ejemplo más simple de una función recursiva:
| Esquema | C |
|---|---|
| ( define ( factorial n ) ( if ( = n 0 ) 1 ( * n ( factorial ( - n 1 ))))) | int factorial ( int n ) { devolver ( n == 0 ) ? 1 : n * factorial ( n -1 ); } |
En este ejemplo, a pesar de que la llamada recursiva está en el último lugar del texto de la función, la optimización automática de la recursividad no funcionará, ya que de hecho la última operación realizada es la operación de multiplicar por n , lo que significa que la cola no se cumple la condición de recurrencia. Las variantes recursivas de cola anteriores para calcular el factorial son una modificación del método obvio, que tiene como objetivo preciso transferir la operación de multiplicación. El método utilizado para esto, por cierto, es una de las formas típicas de llevar la recursividad a una forma recursiva de cola. Se encuentra en el hecho de que un conjunto de datos locales que deben guardarse durante una llamada recursiva se transfiere a los parámetros de llamada de función. En el caso de los ejemplos dados de cálculo factorial, este parámetro es la variable accen la que se acumula el resultado.
En general, tales modificaciones pueden ser bastante no triviales. En particular, una variante es posible cuando solo una, la rama más "problemática" de la ejecución de la función, se hace recursiva a la cola, mientras que el resto permanece recursivo.