En informática , la recursión anónima es una recursión que no llama explícitamente a una función por su nombre. Esto se puede hacer de forma explícita, utilizando una función de orden superior (pasando una función como argumento y llamándola) o de forma implícita, mediante funciones de reflexión que permiten acceder a determinadas funciones en función del contexto actual, especialmente "la función actual" o, a veces, "la función que llama a la función actual".
En la práctica de la programación, la recursión anónima se utiliza sobre todo en JavaScript , que ofrece funciones de reflexión para respaldarla. Sin embargo, en la práctica de la programación general, esto se considera un estilo deficiente y se sugiere en su lugar la recursión con funciones nombradas. La recursión anónima mediante el paso explícito de funciones como argumentos es posible en cualquier lenguaje que admita funciones como argumentos, aunque esto rara vez se utiliza en la práctica, ya que es más largo y menos claro que la recursión explícita por nombre.
En informática teórica, la recursión anónima es importante, ya que demuestra que se puede implementar la recursión sin necesidad de funciones con nombre. Esto es particularmente importante para el cálculo lambda , que tiene funciones unarias anónimas, pero es capaz de calcular cualquier función recursiva. Esta recursión anónima se puede producir de forma genérica mediante combinadores de punto fijo .
La recursión anónima se utiliza principalmente para permitir la recursión de funciones anónimas , particularmente cuando forman cierres o se utilizan como devoluciones de llamadas , para evitar tener que vincular el nombre de la función.
La recursión anónima consiste principalmente en llamar a "la función actual", lo que da como resultado una recursión directa . La recursión indirecta anónima es posible, por ejemplo, llamando al "llamador (la función anterior)" o, más raramente, yendo más arriba en la pila de llamadas , y esto se puede encadenar para producir una recursión mutua . La autorreferencia de "la función actual" es un equivalente funcional de la palabra clave " this " en la programación orientada a objetos , que permite hacer referencia al contexto actual.
La recursión anónima también se puede utilizar para funciones con nombre, en lugar de llamarlas por su nombre, por ejemplo, para especificar que se está recurriendo a la función actual o para permitir cambiar el nombre de la función sin necesidad de cambiar el nombre en el que se llama a sí misma. Sin embargo, como cuestión de estilo de programación, esto no suele hacerse.
La alternativa habitual es utilizar funciones con nombre y recursión con nombre. Dada una función anónima, esto se puede hacer ya sea vinculando un nombre a la función, como en las expresiones de función con nombre en JavaScript, o asignando la función a una variable y luego llamando a la variable, como en las declaraciones de función en JavaScript. Dado que los lenguajes que permiten funciones anónimas generalmente permiten asignar estas funciones a variables (si no son funciones de primera clase), muchos lenguajes no proporcionan una forma de hacer referencia a la función en sí y rechazan explícitamente la recursión anónima; algunos ejemplos incluyen Go . [1]
Por ejemplo, en JavaScript la función factorial se puede definir mediante recursión anónima de la siguiente manera: [2]
[ 1 , 2 , 3 , 4 , 5 ]. mapa ( función ( n ) { retorno ( ! ( n > 1 )) ? 1 : argumentos . callee ( n - 1 ) * n ; }); Reescrito para utilizar una expresión de función nombrada da como resultado:
[ 1 , 2 , 3 , 4 , 5 ]. mapa ( función factorial ( n ) { retorno ( ! ( n > 1 )) ? 1 : factorial ( n - 1 ) * n ; }); Incluso sin mecanismos para hacer referencia a la función actual o a la función que llama, la recursión anónima es posible en un lenguaje que permite funciones como argumentos. Esto se hace añadiendo otro parámetro a la función recursiva básica y utilizando este parámetro como la función para la llamada recursiva. Esto crea una función de orden superior, y pasar esta función superior en sí misma permite la recursión anónima dentro de la función recursiva real. Esto se puede hacer de forma puramente anónima aplicando un combinador de punto fijo a esta función de orden superior. Esto es principalmente de interés académico, en particular para demostrar que el cálculo lambda tiene recursión, ya que la expresión resultante es significativamente más complicada que la función recursiva nombrada originalmente. Por el contrario, el uso de combinadores de punto fijo puede denominarse genéricamente "recursión anónima", ya que este es un uso notable de ellos, aunque tienen otras aplicaciones. [3] [4]
A continuación se muestra un ejemplo con Python. Primero, una recursión estándar con nombre:
def fact ( n ): si n == 0 : devuelve 1 devuelve n * fact ( n - 1 )Usar una función de orden superior para que la función de nivel superior recurra de forma anónima en un argumento, pero aún necesite la función recursiva estándar como argumento:
def fact0 ( n0 ): si n0 == 0 : devuelve 1 devuelve n0 * fact0 ( n0 - 1 ) fact1 = lambda f , n1 : 1 si n1 == 0 de lo contrario n1 * f ( n1 - 1 ) fact = lambda n : fact1 ( fact0 , n )Podemos eliminar la función recursiva estándar pasando el argumento de la función en la llamada:
hecho1 = lambda f , n1 : 1 si n1 == 0 de lo contrario n1 * f ( f , n1 - 1 ) hecho = lambda n : hecho1 ( hecho1 , n )La segunda línea se puede reemplazar por una función genérica de orden superior llamada combinador :
F = lambda f : ( lambda x : f ( f , x )) hecho1 = lambda f , n1 : 1 si n1 == 0 de lo contrario n1 * f ( f , n1 - 1 ) hecho = F ( hecho1 )Escrito anónimamente: [5]
( lambda f : ( lambda x : f ( f , x ))) \ ( lambda g , n1 : 1 si n1 == 0 de lo contrario n1 * g ( g , n1 - 1 ))En el cálculo lambda , que solo utiliza funciones de una sola variable, esto se puede hacer a través del combinador Y. Primero haga que la función de orden superior de dos variables sea una función de una sola variable, que devuelva directamente una función, mediante currying :
hecho1 = lambda f : ( lambda n1 : 1 si n1 == 0 de lo contrario n1 * f ( f )( n1 - 1 )) hecho = hecho1 ( hecho1 )Aquí hay dos operaciones de "aplicación de una función de orden superior a sí misma": f(f)en la primera línea y fact1(fact1)en la segunda. Al factorizar la segunda aplicación doble en un combinador se obtiene:
C = lambda x : x ( x ) hecho1 = lambda f : ( lambda n1 : 1 si n1 == 0 de lo contrario n1 * f ( f )( n1 - 1 )) hecho = C ( hecho1 )Al factorizar la otra aplicación doble se obtiene:
C = lambda x : x ( x ) D = lambda f : ( lambda x : f ( lambda v : x ( x )( v ))) hecho1 = lambda g : ( lambda n1 : 1 si n1 == 0 de lo contrario n1 * g ( n1 - 1 )) hecho = C ( D ( hecho1 ))Combinando los dos combinadores en uno se obtiene el combinador Y :
C = lambda x : x ( x ) D = lambda f : ( lambda x : f ( lambda v : x ( x )( v ))) Y = lambda y : C ( D ( y )) hecho1 = lambda g : ( lambda n1 : 1 si n1 == 0 de lo contrario n1 * g ( n1 - 1 )) hecho = Y ( hecho1 )Desarrollando el combinador Y obtenemos:
Y = lambda f : ( lambda x : f ( lambda v : x ( x )( v ))) \ ( lambda x : f ( lambda v : x ( x )( v ))) hecho1 = lambda g : ( lambda n1 : 1 si n1 == 0 de lo contrario n1 * g ( n1 - 1 )) hecho = Y ( hecho1 )La combinación de estos produce una definición recursiva del factorial en el cálculo lambda (funciones anónimas de una sola variable): [6]
( lambda f : ( lambda x : f ( lambda v : x ( x )( v ))) ( lambda x : f ( lambda v : x ( x )( v )))) \ ( lambda g : ( lambda n1 : 1 si n1 == 0 de lo contrario n1 * g ( n1 - 1 )))En APL , se puede acceder a la función de función de función∇ actual a través de . Esto permite la recursión anónima, como en esta implementación del factorial:
{ 0 = ⍵: 1 ⋄ ⍵ × ∇ ⍵ - 1 } 5 120 { 0 = ⍵ : 1 ⋄ ⍵ × ∇ ⍵ - 1 } ¨ ⍳ 10 ⍝ aplicado a cada elemento de 0 a 9 1 1 2 6 24 120 720 5040 40320 362880 En JavaScript , la función actual es accesible a través de arguments.callee, mientras que la función que la llama es accesible a través de arguments.caller. Estos permiten la recursión anónima, como en esta implementación del factorial: [2]
[ 1 , 2 , 3 , 4 , 5 ]. mapa ( función ( n ) { retorno ( ! ( n > 1 )) ? 1 : argumentos . callee ( n - 1 ) * n ; }); A partir de Perl 5.16, se puede acceder a la subrutina actual a través del __SUB__token, que devuelve una referencia a la subrutina actual, o undeffuera de una subrutina. [7] Esto permite la recursión anónima, como en la siguiente implementación del factorial:
#!/usr/bin/perl utiliza la característica ":5.16" ; imprimir sub { mi $x = shift ; $x > 0 ? $x * __SUB__ -> ( $x - 1 ) : 1 ; } -> ( 5 ), "\n" ; En R , la función actual se puede llamar mediante Recall. Por ejemplo,
sapply ( 0 : 5 , función ( n ) { si ( n == 0 ) devolver ( 1 ) n * Recordar ( n - 1 ) }) Sin embargo, no funcionará si se pasa como argumento a otra función, por ejemplo lapply, dentro de la definición de función anónima. En este caso, sys.function(0)se puede utilizar . [8] Por ejemplo, el código siguiente eleva al cuadrado una lista de forma recursiva:
( función ( x ) { si ( es.lista ( x )) { lapply ( x , sys.función ( 0 )) } de lo contrario { x ^ 2 } })( lista ( lista ( 1 , 2 , 3 ), lista ( 4 , 5 )))