Llamada de cola

En informática , una llamada de cola es una llamada a una subrutina que se ejecuta como acción final de un procedimiento. ^{[ 1 ]} Si el destino de una llamada de cola es la misma subrutina, se dice que la subrutina es recursiva de cola , que es un caso especial de recursión directa . La recursión de cola (o recursión de extremo de cola ) es particularmente útil y suele ser fácil de optimizar en las implementaciones.

Las llamadas de cola se pueden implementar sin agregar un nuevo marco de pila a la pila de llamadas . La mayor parte del marco del procedimiento actual ya no es necesaria y se puede reemplazar por el marco de la llamada de cola, modificado según corresponda (similar a la superposición para procesos, pero para llamadas a funciones). El programa puede entonces saltar a la subrutina llamada. Generar este código en lugar de una secuencia de llamadas estándar se denomina eliminación de llamadas de cola u optimización de llamadas de cola . La eliminación de llamadas de cola permite que las llamadas a procedimientos en posición de cola se implementen con la misma eficiencia que las instrucciones goto , lo que permite una programación estructurada eficiente . En palabras de Guy L. Steele , "en general, las llamadas a procedimientos pueden considerarse como instrucciones GOTO que también pasan parámetros y se pueden codificar uniformemente como instrucciones JUMP [en código máquina]". ^{[ 2 ]}

No todos los lenguajes de programación requieren la eliminación de llamadas recursivas de cola. Sin embargo, en los lenguajes de programación funcional , la eliminación de llamadas recursivas de cola suele estar garantizada por el estándar del lenguaje , lo que permite que la recursión de cola utilice una cantidad de memoria similar a la de un bucle equivalente . El caso especial de las llamadas recursivas de cola, cuando una función se llama a sí misma, puede ser más susceptible a la eliminación de llamadas que las llamadas recursivas de cola generales. Cuando la semántica del lenguaje no admite explícitamente las llamadas recursivas de cola generales, un compilador a menudo aún puede optimizar las llamadas entre hermanos , o las llamadas recursivas de cola a funciones que toman y devuelven los mismos tipos que la función que las llama. ^{[ 3 ]}

Descripción

Cuando se llama a una función, el ordenador debe "recordar" el lugar desde donde se realizó la llamada, la dirección de retorno , para poder regresar a esa ubicación con el resultado una vez completada la llamada. Normalmente, esta información se guarda en la pila de llamadas , una lista de ubicaciones de retorno en el orden en que se alcanzaron las ubicaciones de llamada. Además, los compiladores asignan memoria para las variables locales de la función llamada y colocan el contenido de los registros (si los hay y/o son relevantes) en la pila. Por lo general, esto se hace asignando un marco de pila que incluye los registros guardados, el espacio asignado para las variables locales que no son registros, la dirección de retorno y los parámetros de llamada (a menos que se pasen en registros). Para las llamadas recursivas, no es necesario recordar quién realizó la llamada ni conservar el contenido de los registros; en su lugar, la eliminación de llamadas recursivas evita la asignación de nuevos marcos de pila y realiza solo los cambios mínimos necesarios en el marco de pila existente antes de pasarlo, y la función llamada recursivamente regresará directamente a quien realizó la llamada original . ^{[ 4 ]} Sin embargo, esto conlleva la pérdida total del marco de pila de la función que realiza la llamada, lo que a veces se considera un obstáculo para la depuración. La llamada recursiva no tiene por qué aparecer léxicamente después de todas las demás instrucciones en el código fuente; solo es importante que la función que realiza la llamada retorne inmediatamente después de la llamada recursiva, devolviendo el resultado de esta última si lo hay, ya que la función que realiza la llamada se omite cuando se realiza la optimización.

Para llamadas a funciones no recursivas, esta suele ser una optimización que ahorra poco tiempo y espacio, ya que no hay muchas funciones diferentes disponibles para llamar. Sin embargo, al tratar con funciones recursivas o mutuamente recursivas donde la recursión ocurre a través de llamadas de cola, el espacio de pila y la cantidad de retornos ahorrados pueden llegar a ser muy significativos, ya que una función puede llamarse a sí misma, directa o indirectamente, creando un nuevo marco de pila de llamadas cada vez. La eliminación de llamadas de cola a menudo reduce los requisitos asintóticos de espacio de pila de lineal, u O (n), a constante, u O(1). Por lo tanto, la eliminación de llamadas de cola es requerida por las definiciones estándar de algunos lenguajes de programación, como Scheme , y lenguajes de la familia ML , entre otros. ^{[ 5 ]}^{[ 6 ]} La definición del lenguaje Scheme formaliza la noción intuitiva de posición de cola exactamente, al especificar qué formas sintácticas permiten tener resultados en contexto de cola. ^{[ 7 ]} Las implementaciones que permiten que un número ilimitado de llamadas de cola estén activas al mismo tiempo, gracias a la eliminación de llamadas de cola, también pueden llamarse "propiamente recursivas de cola". ^{[ 5 ]}

Además del espacio y la eficiencia de ejecución, la eliminación de llamadas recursivas es importante en el estilo de programación funcional conocido como estilo de paso de continuaciones (CPS), que de otro modo se quedaría rápidamente sin espacio en la pila.

Forma sintáctica

Una llamada recursiva de cola puede ubicarse justo antes del final sintáctico de una función.

int a ( int n ); int b ( int n );int foo ( int data ) { a ( data ); return b ( data ); }

Aquí, tanto a(data)como b(data)son llamadas, pero bes lo último que ejecuta el procedimiento antes de regresar y, por lo tanto, se encuentra en posición de cola. Sin embargo, no todas las llamadas de cola se ubican necesariamente al final sintáctico de una subrutina:

int c ( int n );int bar ( int data ) { if ( a ( data ) > 0 ) { return b ( data ); } return c ( data ); }

Aquí, ambas llamadas a by cestán en posición de cola. Esto se debe a que cada una de ellas se encuentra al final de la rama if respectivamente, aunque la primera no esté sintácticamente al final del barcuerpo de .

Consideremos este ejemplo:

int foo1 ( int data ) { return a ( data ) + 1 ; }int foo2 ( int data ) { int ret = a ( data ); return ret ; }int foo3 ( int data ) { int ret = a ( data ); return ( ret == 0 ) ? 1 : ret ; }

La llamada a a(data)está en posición de cola en , pero nofoo2 está en posición de cola ni en ni en , porque el control debe regresar al llamador para permitirle inspeccionar o modificar el valor de retorno antes de devolverlo.foo1foo3

Programas de ejemplo

El siguiente programa es un ejemplo en Scheme : ^{[ 8 ]}

;; factorial : número -> número ;; para calcular el producto de todos los enteros positivos ;; menores o iguales a n. ( define ( factorial n ) ( if ( = n 0 ) 1 ( * n ( factorial ( - n 1 )))))

Esto no está escrito en un estilo recursivo de cola, porque la función de multiplicación ("*") está en la posición de cola. Esto se puede comparar con:

;; factorial : número -> número ;; para calcular el producto de todos los enteros positivos ;; menores o iguales a n. ( define ( factorial n ) ( fact-iter 1 n )) ( define ( fact-iter producto n ) ( if ( = n 0 ) producto ( fact-iter ( * producto n ) ( - n 1 ))))

Este programa asume una evaluación en orden aplicativo . El procedimiento interno fact-iterse llama a sí mismo al final del flujo de control. Esto permite que un intérprete o compilador reorganice la ejecución, que normalmente se vería así: ^{[ 8 ]}

 llamar factorial (4) llamar fact-iter (1 4) llamar fact-iter (4 3) llamar fact-iter (12 2) llamar fact-iter (24 1) regresar 24 regresar 24 regresar 24 regresar 24 regresar 24

en la variante más eficiente , tanto en términos de espacio como de tiempo:

 llamar factorial (4) llamar fact-iter (1 4) Reemplazar argumentos con (4 3) Reemplazar argumentos con (12 2) reemplazar argumentos con (24 1) regresar 24 regresar 24

Esta reorganización ahorra espacio, ya que no es necesario guardar ningún estado, salvo la dirección de la función que realiza la llamada, ni en la pila ni en el montón, y el marco de pila de llamadas fact-iterse reutiliza para almacenar los resultados intermedios. Esto también significa que el programador no tiene que preocuparse por quedarse sin espacio en la pila o el montón en recursiones extremadamente profundas. En implementaciones típicas, la variante recursiva de cola será sustancialmente más rápida que la otra variante, pero solo por un factor constante.

Algunos programadores que trabajan con lenguajes funcionales reescriben el código recursivo para que sea recursivo de cola y así aprovechar esta característica. Esto suele requerir la adición de un argumento "acumulador" ( productcomo en el ejemplo anterior) a la función.

Recursión de cola módulo cons

La recursión de cola módulo cons es una generalización de la optimización de recursión de cola introducida por David HD Warren ^{[ 9 ]} en el contexto de la compilación de Prolog , considerado un lenguaje de configuración explícita . Fue descrita (aunque no nombrada) por Daniel P. Friedman y David S. Wise en 1974 ^[¹⁰^] como una técnica de compilación de LISP . Como su nombre indica, se aplica cuando la única operación que queda por realizar tras una llamada recursiva es anteponer un valor conocido a la lista devuelta (o realizar un número constante de operaciones simples de construcción de datos, en general). Esta llamada sería, por lo tanto, una llamada de cola salvo (" módulo ") por la operación cons . Pero anteponer un valor al inicio de una lista al salir de una llamada recursiva es lo mismo que añadir este valor al final de la lista creciente al entrar en la llamada recursiva, construyendo así la lista como un efecto secundario , como si fuera un parámetro acumulador implícito. El siguiente fragmento de Prolog ilustra el concepto:

Código de ejemplo

Así, en la traducción recursiva de cola, dicha llamada se transforma en la creación de un nuevo nodo de lista y la configuración de su firstcampo, para luego realizar la llamada recursiva de cola con el puntero al restcampo del nodo como argumento, que se rellenará recursivamente. El mismo efecto se logra cuando la recursión se protege mediante un constructor de datos de evaluación diferida, lo cual se consigue automáticamente en lenguajes de programación perezosos como Haskell.

Ejemplo en C

El siguiente fragmento define una función recursiva en C que duplica una lista enlazada (con algunos códigos equivalentes en Scheme y Prolog como comentarios, para su comparación):

En esta forma, la función no es recursiva de cola, porque el control regresa al llamador después de que la llamada recursiva duplica el resto de la lista de entrada. Incluso si asignara el nodo de cabeza antes de duplicar el resto, aún necesitaría insertar el resultado de la llamada recursiva en el nextcampo después de la llamada. ^{[ a ]} Por lo tanto, la función es casi recursiva de cola. El método de Warren traslada la responsabilidad de llenar el nextcampo a la propia llamada recursiva, que por lo tanto se convierte en una llamada de cola. ^{[ b ]} Usando un nodo de cabeza centinela para simplificar el código,

Ahora, la función llamada agrega el elemento al final de la lista creciente, en lugar de que la función que realiza la llamada lo agregue al principio de la lista devuelta. El trabajo se realiza ahora avanzando desde el inicio de la lista, antes de la llamada recursiva que continúa, en lugar de retroceder desde el final de la lista, una vez que la llamada recursiva ha devuelto su resultado. Por lo tanto, es similar a la técnica de acumulación de parámetros, que convierte un cálculo recursivo en uno iterativo.

Como es característico de esta técnica, se crea un marco padre en la pila de llamadas de ejecución, que la función llamada recursiva de cola puede reutilizar como su propio marco de llamada si la optimización de llamadas de cola está presente.

La implementación recursiva de cola ahora se puede convertir en una implementación iterativa explícita, como un bucle acumulativo :

Historia

En un artículo presentado en la conferencia ACM de Seattle en 1977, Guy L. Steele resumió el debate sobre la instrucción GOTO y la programación estructurada , y observó que las llamadas a procedimientos en la posición final de un procedimiento pueden tratarse mejor como una transferencia directa de control al procedimiento llamado, eliminando típicamente las operaciones innecesarias de manipulación de la pila. ^{[ 2 ]} Dado que tales "llamadas finales" son muy comunes en Lisp , un lenguaje donde las llamadas a procedimientos son omnipresentes, esta forma de optimización reduce considerablemente el costo de una llamada a procedimiento en comparación con otras implementaciones. Steele argumentó que las llamadas a procedimientos mal implementadas habían llevado a la percepción artificial de que la instrucción GOTO era barata en comparación con la llamada a procedimiento. Steele argumentó además que "en general, las llamadas a procedimientos pueden considerarse útiles como instrucciones GOTO que también pasan parámetros, y pueden codificarse uniformemente como instrucciones JUMP [en código máquina]", considerando las instrucciones de manipulación de la pila en código máquina "una optimización (¡en lugar de al revés!)". ^{[ 2 ]} Steele citó evidencia de que los algoritmos numéricos bien optimizados en Lisp podían ejecutarse más rápido que el código producido por los compiladores Fortran comerciales disponibles en ese momento porque el costo de una llamada a procedimiento en Lisp era mucho menor. En Scheme , un dialecto de Lisp desarrollado por Steele con Gerald Jay Sussman , la eliminación de llamadas recursivas está garantizada para ser implementada en cualquier intérprete. ^{[ 11 ]}

Métodos de implementación

La recursión de cola es importante para algunos lenguajes de alto nivel , especialmente los lenguajes funcionales y lógicos y los miembros de la familia Lisp . En estos lenguajes, la recursión de cola es la forma más común (y a veces la única disponible) de implementar la iteración. La especificación del lenguaje Scheme requiere que las llamadas de cola se optimicen para no aumentar el tamaño de la pila. Las llamadas de cola se pueden realizar explícitamente en Perl , con una variante de la instrucción "goto" que toma un nombre de función: goto &NAME;^{[ 12 ]}

Sin embargo, para las implementaciones de lenguaje que almacenan argumentos de función y variables locales en una pila de llamadas (que es la implementación predeterminada para muchos lenguajes, al menos en sistemas con pila de hardware , como el x86 ), implementar la optimización generalizada de llamadas recursivas de cola (incluida la recursión de cola mutua) presenta un problema: si el tamaño del registro de activación de la función llamada es diferente al de la función que la llama, puede ser necesario realizar una limpieza adicional o redimensionar el marco de pila. En estos casos, optimizar la recursión de cola sigue siendo trivial, pero la optimización general de llamadas recursivas de cola puede ser más difícil de implementar de manera eficiente.

Por ejemplo, en la máquina virtual de Java (JVM), las llamadas recursivas de cola se pueden eliminar (ya que reutilizan la pila de llamadas existente), pero las llamadas de cola generales no se pueden eliminar (ya que modifican la pila de llamadas). ^{[ 13 ]}^{[ 14 ]} Como resultado, los lenguajes funcionales como Scala , que se ejecutan en la JVM, pueden implementar de manera eficiente la recursión de cola directa, pero no la recursión de cola mutua.

Los conjuntos de compiladores GCC , LLVM/Clang e Intel realizan optimización de llamadas recursivas para C y otros lenguajes en niveles de optimización más altos o cuando -foptimize-sibling-callsse pasa la opción. ^{[ 15 ]}^{[ 16 ]}^{[ 17 ]} Aunque la sintaxis del lenguaje en cuestión no lo admita explícitamente, el compilador puede realizar esta optimización siempre que pueda determinar que los tipos de retorno para la función que llama y la función llamada son equivalentes, y que los tipos de argumentos pasados a ambas funciones son iguales o requieren la misma cantidad de espacio de almacenamiento total en la pila de llamadas. ^{[ 18 ]}

Existen diversos métodos de implementación.

En el ensamblaje

Las llamadas de cola suelen ser optimizadas por intérpretes y compiladores de lenguajes de programación funcional y lógica para convertirse en formas de iteración más eficientes . Por ejemplo, los programadores de Scheme suelen expresar los bucles while como llamadas a procedimientos en posición de cola y confían en el compilador o intérprete de Scheme para sustituir las llamadas de cola por instrucciones de salto más eficientes . ^{[ 19 ]}

Para los compiladores que generan código ensamblador directamente, la eliminación de llamadas recursivas es sencilla: basta con reemplazar un código de operación de llamada por uno de salto, después de fijar los parámetros en la pila. Desde la perspectiva del compilador, el primer ejemplo anterior se traduce inicialmente a un lenguaje pseudo-ensamblador (de hecho, se trata de código ensamblador x86 válido ):

foo: llama a B llama a A ret

La eliminación de llamadas de cola reemplaza las dos últimas líneas con una única instrucción de salto:

foo: llama a B salta a A

Una vez que la subrutina Ase complete, regresará directamente a la dirección de retorno de foo, omitiendo la retinstrucción innecesaria.

Normalmente, las subrutinas que se llaman necesitan recibir parámetros . Por lo tanto, el código generado debe asegurarse de que el marco de llamada para A esté configurado correctamente antes de saltar a la subrutina llamada al final. Por ejemplo, en plataformas donde la pila de llamadas no solo contiene la dirección de retorno , sino también los parámetros de la subrutina, el compilador puede necesitar emitir instrucciones para ajustar la pila de llamadas. En una plataforma de este tipo, para el código:

función foo(datos1, datos2) B(datos1) devolver A(datos2)

(donde data1y data2son parámetros) un compilador podría traducir eso como: ^{[ c ]}

foo:mov reg ,[ sp + data1 ] ; obtiene el parámetro data1 de la pila (sp) en un registro temporal.push reg ; coloca data1 en la pila donde B lo esperallamar a B ; B utiliza datos1pop ; elimina data1 de la pilamov reg ,[ sp + data2 ] ; obtiene el parámetro data2 de la pila (sp) en un registro temporal.push reg ; coloca data2 en la pila donde A lo esperallamar A ; A utiliza datos2pop ; elimina data2 de la pila.retirado

Un optimizador de llamadas recursivas podría entonces cambiar el código a:

foo:mov reg ,[ sp + data1 ] ; obtiene el parámetro data1 de la pila (sp) en un registro temporal.push reg ; coloca data1 en la pila donde B lo esperallamar a B ; B utiliza datos1pop ; elimina data1 de la pilamov reg ,[ sp + data2 ] ; obtiene el parámetro data2 de la pila (sp) en un registro temporal.mov [ sp + data1 ], reg ; coloca data2 donde A lo esperajmp A ; A utiliza data2 y regresa inmediatamente a quien la llamó.

Este código es más eficiente tanto en términos de velocidad de ejecución como de uso del espacio de la pila.

Desde la perspectiva del compilador, una llamada recursiva pura es más visible en las funciones recursivas. Consideremos un ejemplo de pseudo-ensamblador donde una función se llama a sí misma como su acción final para procesar datos, tomando un único parámetro:

función foo ( datos ) si ( datos == 0 ) devolver datos devolver foo ( datos - 1 )

Un compilador no optimizado traduce esto en una secuencia de llamadas estándar, insertando un nuevo marco en la pila por cada recursión:

foo: mov reg ,[ sp + data ] ; obtener datos de la pila parámetro cmp reg , 0 ; comprobación del caso base je end dec reg ; modificar datos push reg ; insertar nuevos datos en la pila para la siguiente llamada call foo ; llamada recursiva (AGRANDA LA PILA) pop ; limpiar la pila después del retorno end: ret

Un optimizador de llamadas recursivas reconoce que el marco de pila actual ya no es necesario después de la llamada. Modifica el código para actualizar destructivamente el argumento en el mismo lugar y saltar, limitando la pila estrictamente a un espacio $O (1)$ :

foo: mov reg ,[ sp + data ] ; obtener datos del parámetro de pila cmp reg , 0 ; comprobación del caso base je end dec reg ; modificar datos mov [ sp + data ], reg ; actualizar destructivamente el parámetro de pila existente jmp foo ; saltar directamente de vuelta al inicio (LA PILA PERMANECE LIMITADA) end: ret

Este código optimizado es físicamente idéntico a un bucle `while` imperativo, que se ejecuta con una memoria estrictamente limitada y a máxima velocidad.

Complejidad del hardware y del espacio

En entornos bare-metal y en la teoría de autómatas formales, una llamada de cola pura se define principalmente por su complejidad espacial: una llamada de cola pura se produce cuando el espacio de la pila está estrictamente limitado durante la recursión . Al garantizar que el puntero de pila no crezca proporcionalmente a la profundidad de la recursión, las llamadas de cola permiten que la evaluación recursiva de profundidad infinita opere dentro de estrictas restricciones de memoria física (como un microkernel o un sector de arranque ). Esto transforma físicamente la pila de llamadas en una máquina de estados limitada.

Relación con las corrutinas

Una llamada recursiva sin retorno es físicamente equivalente a una JMPinstrucción de ensamblador. Esta propiedad convierte a la llamada recursiva en una primitiva fundamental para implementar corrutinas de alto rendimiento . Al reemplazar el ciclo tradicional CALLcon RETun salto directo al siguiente estado, un motor de ejecución puede transferir el control entre diferentes unidades funcionales con un espacio de pila constante. Este mecanismo es fundamental para el estilo de paso de continuaciones , donde el programa nunca regresa, sino que realiza una secuencia de llamadas recursivas para transitar entre estados cooperativos.

A través del trampolín

Dado que muchos compiladores de Scheme utilizan C como código intermedio, la recursión de cola debe codificarse en C sin aumentar la pila, incluso si el compilador de C no optimiza las llamadas recursivas de cola. Muchas implementaciones lo logran mediante un mecanismo conocido como trampolín , un fragmento de código que llama repetidamente a funciones. Todas las funciones se acceden a través del trampolín. Cuando una función debe llamar a otra recursiva de cola, en lugar de llamarla directamente y devolver el resultado, devuelve la dirección de la función a llamar y los parámetros de llamada al trampolín (desde el cual fue llamada), y el trampolín se encarga de llamar a esta función a continuación con los parámetros especificados. Esto garantiza que la pila de C no aumente y que la iteración pueda continuar indefinidamente.

Es posible implementar trampolines utilizando funciones de orden superior en lenguajes que las admiten, como Groovy , Visual Basic .NET y C# . ^{[ 20 ]}

Usar un trampolín para todas las llamadas a funciones es bastante más costoso que la llamada a función C normal, por lo que al menos un compilador de Scheme, Chicken , utiliza una técnica descrita por primera vez por Henry Baker a partir de una sugerencia no publicada de Andrew Appel , ^{[ 21 ]} en la que se utilizan llamadas C normales pero el tamaño de la pila se verifica antes de cada llamada. Cuando la pila alcanza su tamaño máximo permitido, los objetos en la pila se recolectan mediante el recolector de basura utilizando el algoritmo de Cheney moviendo todos los datos activos a un montón separado. Después de esto, la pila se desenrolla ("popped") y el programa se reanuda desde el estado guardado justo antes de la recolección de basura. Baker dice "El método de Appel evita hacer una gran cantidad de pequeños rebotes de trampolín saltando ocasionalmente desde el Empire State Building". ^{[ 21 ]} La recolección de basura asegura que la recursión de cola mutua puede continuar indefinidamente. Sin embargo, este enfoque requiere que ninguna llamada a función C regrese nunca, ya que no hay garantía de que el marco de pila de su llamador todavía exista; por lo tanto, implica una reescritura interna mucho más drástica del código del programa: estilo de paso de continuaciones .

Relación con la `while`declaración

La recursión de cola puede relacionarse con la instrucción while , una iteración explícita, por ejemplo, mediante la transformación

procedimiento foo( x ) si p ( x ) devolver bar( x ) sino devolver foo(baz( x ))

en

procedimiento foo( x ) mientras sea verdadero si p ( x ) devolver bar( x ) sino x ← baz( x )

donde x puede ser una tupla que involucra más de una variable: en ese caso, se debe tener cuidado al implementar la instrucción de asignación x ← baz( x ) para que se respeten las dependencias. Puede ser necesario introducir variables auxiliares o usar una construcción de intercambio .

En términos más generales,

procedimiento foo( x ) si p ( x ) devolver bar( x ) sino si q ( x ) devolver baz( x ) ... else if r ( x ) return foo(qux( x )) ... de lo contrario, devuelve foo(quux( x ))

puede transformarse en

procedimiento foo( x ) mientras sea verdadero si p ( x ) devolver bar( x ) sino si q ( x ) devolver baz( x ) ... else if r ( x ) x ← qux( x ) ... else x ← quux( x )

Por ejemplo, este programa de Julia proporciona una definición recursiva no de cola factorialdel factorial:

función factorial ( n :: Entero ) :: Enterosi n == 0devolver 1demásdevolver n * factorial ( n - 1 )finfin

En efecto, n * factorial(n - 1)envuelve la llamada a factorial. Pero puede transformarse en una definición recursiva de cola añadiendo un argumento allamado acumulador . ^{[ 8 ]}

Este programa de Julia proporciona una definición recursiva de cola factorialdel factorial:

función factorial ( n :: Integer , a :: Integer ) :: Integer si n == 0 : devolver a sino devolver factorial ( n - 1 , n * a ) fin finfunción factorial ( n :: Integer ) :: Integer return factorial ( n , 1 ) fin

Este programa de Julia proporciona una definición iterativa fact_iterdel factorial:

función fact_iter ( n :: Integer , a :: Integer ) :: Integer mientras n > 0 a = n * a n = n - 1 fin devolver a finfunción factorial ( n :: Entero ) :: Entero devuelve fact_iter ( n , one ( n )) fin

Soporte de idiomas

Clojure – Clojure tiene recuruna forma especial. ^{[ 22 ]}
Common Lisp : algunas implementaciones realizan optimización de llamadas recursivas durante la compilación si se busca optimizar la velocidad.
Elixir – Elixir implementa la optimización de llamadas recursivas, ^{[ 23 ]} al igual que todos los lenguajes que actualmente apuntan a la máquina virtual BEAM.
Olmo – Sí ^{[ 24 ]}
Erlang – Sí
F# – F# implementa TCO por defecto siempre que sea posible ^{[ 25 ]}
Ir – Sin soporte ^{[ 26 ]}
Haskell – Sí ^{[ 27 ]}
JavaScript – Los motores compatibles con ECMAScript 6.0 deberían tener llamadas recursivas ^{[ 28 ]} , lo cual ahora está implementado en Safari / WebKit ^{[ 29 ]} pero rechazado por V8 y SpiderMonkey.
Kotlin – Tiene tailrecmodificador para funciones ^{[ 30 ]}
Lua – La recursión de cola es requerida por la definición del lenguaje ^{[ 31 ]}
Objective-C : el compilador optimiza las llamadas de cola cuando se especifica la opción -O1 (o superior), pero se ve fácilmente afectado por las llamadas añadidas por el conteo automático de referencias .
OCaml – Sí. Desde la versión 4.03.0, ^[³²^] el atributo integrado se puede usar para verificar que una llamada se optimizará, emitiendo una advertencia en caso contrario. ^[³³^]tailcall
Perl – Explícito con una variante de la instrucción "goto" que toma un nombre de función: goto &NAME;^{[ 34 ]}
Prolog – SWI-Prolog implementa la optimización de recursión de cola. ^{[ 35 ]}
PureScript – Sí
Python – Las implementaciones estándar de Python no realizan optimización de llamadas recursivas, aunque existe un módulo de terceros para ello. ^{[ 36 ]} El inventor del lenguaje, Guido van Rossum, sostuvo que las trazas de pila se alteran al eliminar las llamadas recursivas, lo que dificulta la depuración, y prefirió que los programadores utilizaran la iteración explícita en su lugar. ^{[ 37 ]} En Python 3.14, se introdujo un nuevo intérprete que utiliza el despacho de códigos de operación de Python basado en llamadas recursivas. ^{[ 38 ]} Esto resultó en un rendimiento general mejorado en comparación con Python 3.13. ^{[ 39 ]}^{[ 40 ]}
R – Sí, tailcall()función introducida en R.4.4.0 ^{[ 41 ]}
Raqueta – Sí ^{[ 42 ]}
Ruby – Sí, pero deshabilitado por defecto ^{[ 43 ]}
Rust : la optimización de llamadas recursivas puede realizarse en circunstancias limitadas, pero no está garantizada ^{[ 44 ].}
Scala – Las funciones recursivas de cola son optimizadas automáticamente por el compilador. Estas funciones también pueden marcarse opcionalmente con una @tailrecanotación, lo que provoca un error de compilación si la función no es recursiva de cola ^{[ 45 ].}
Esquema – Requerido por la definición del lenguaje ^{[ 46 ]}^{[ 47 ]}
Rápido – En algunos casos. ^{[ 48 ]}
Tcl – Desde Tcl 8.6, Tcl tiene un tailcallcomando ^{[ 49 ]}
Zig – Sí ^{[ 50 ]}

Véase también

Notas

↑ Así:

if ( ls ) { head = ( LinkedList * ) malloc ( sizeof ( * head )); head -> value = ls -> value ; head -> next = duplicate ( ls -> next ); }