En informática , la recursividad anónima es la recursividad que no llama explícitamente a una función por su nombre. Esto se puede hacer explícitamente, usando una función de orden superior - pasando una función como un argumento y llamándola - o implícitamente, a través de características de reflexión que le permiten a uno acceder a ciertas funciones dependiendo del contexto actual, especialmente "la función actual "oa veces" la función de llamada de la función actual ".
En la práctica de la programación, la recursividad anónima se usa notablemente en JavaScript , que proporciona facilidades de reflexión para respaldarla. En la práctica de programación general, sin embargo, esto se considera un estilo deficiente, y en su lugar se sugiere la recursividad 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 usa en la práctica, ya que es más largo y menos claro que recurrir explícitamente por nombre.
En la informática teórica, la recursividad anónima es importante, ya que muestra que se puede implementar la recursividad sin requerir funciones nombradas. 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 recursividad anónima se puede producir de forma genérica mediante combinadores de punto fijo .
Usar
La recursividad anónima se utiliza principalmente para permitir la recursividad para funciones anónimas , particularmente cuando forman cierres o se utilizan como devoluciones de llamada , para evitar tener que vincular el nombre de la función.
La recursividad anónima consiste principalmente en llamar a "la función actual", lo que da como resultado una recursividad directa . La recursividad indirecta anónima es posible, como llamando al "llamador (la función anterior)" o, más raramente, subiendo más en la pila de llamadas , y esto puede encadenarse para producir recursividad mutua . La autorreferencia de "la función actual" es un equivalente funcional de la palabra clave " this " en la programación orientada a objetos , lo que permite referirse al contexto actual.
La recursividad anónima también se puede usar para funciones con nombre, en lugar de llamarlas por su nombre, digamos para especificar que uno está recurriendo a la función actual, o para permitir que uno cambie el nombre de la función sin necesidad de cambiar el nombre donde se llama a sí misma. Sin embargo, por cuestiones de estilo de programación, esto generalmente no se hace.
Alternativas
Funciones nombradas
La alternativa habitual es utilizar funciones con nombre y recursividad con nombre. Dada una función anónima, esto se puede hacer 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 funciones de primera clase), muchos lenguajes no proporcionan una forma de referirse a la función en sí y rechazan explícitamente la recursividad anónima; los ejemplos incluyen Go . [1]
Por ejemplo, en JavaScript, la función factorial se puede definir mediante recursividad anónima como tal: [2]
[ 1 , 2 , 3 , 4 , 5 ]. mapa ( función ( n ) { retorno ( ! ( n > 1 )) ? 1 : argumentos . callee ( n - 1 ) * n ; });
Reescrito para usar una expresión de función nombrada produce:
[ 1 , 2 , 3 , 4 , 5 ]. mapa ( función factorial ( n ) { retorno ( ! ( n > 1 )) ? 1 : factorial ( n - 1 ) * n ; });
Pasando funciones como argumentos
Incluso sin mecanismos para referirse a la función actual o la función que llama, la recursividad anónima es posible en un lenguaje que permite funciones como argumentos. Esto se hace agregando otro parámetro a la función recursiva básica y usando este parámetro como la función para la llamada recursiva. Esto crea una función de orden superior, y pasando esta función más alta en sí permite la recursividad en el anonimato 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, particularmente para mostrar que el cálculo lambda tiene recursividad, ya que la expresión resultante es significativamente más complicada que la función recursiva con nombre original. Por el contrario, el uso de combinadores de punta fija puede denominarse genéricamente "recursividad anónima", ya que es un uso notable de ellos, aunque tienen otras aplicaciones. [3] [4]
Esto se ilustra a continuación usando Python. Primero, una recursividad estándar con nombre:
def hecho ( n ): si n == 0 : devuelve 1 devuelve n * hecho ( n - 1 )
Usando una función de orden superior para que la función de nivel superior se repita de forma anónima en un argumento, pero aún necesita la función recursiva estándar como argumento:
def fact0 ( n0 ): if n0 == 0 : return 1 return n0 * fact0 ( n0 - 1 ) fact1 = lambda f , n1 : 1 if n1 == 0 else n1 * f ( n1 - 1 ) fact = lambda n : hecho1 ( hecho0 , n )
Podemos eliminar la función recursiva estándar pasando el argumento de la función a la llamada:
fact1 = lambda f , n1 : 1 if n1 == 0 else n1 * f ( f , n1 - 1 ) fact = lambda n : fact1 ( fact1 , 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 )) fact1 = lambda f , n1 : 1 if n1 == 0 else n1 * f ( f , n1 - 1 ) fact = F ( fact1 )
Escrito de forma anónima: [5]
( lambda f : ( lambda x : f ( f , x ))) \ ( lambda g , n1 : 1 si n1 == 0 más n1 * g ( g , n1 - 1 ))
En el cálculo lambda , que sólo utiliza funciones de una sola variable, esto se puede hacer a través de la combinator Y . Primero, haga que la función de orden superior de dos variables sea una función de una sola variable, que devuelve directamente una función, currando :
fact1 = lambda f : ( lambda n1 : 1 if n1 == 0 else n1 * f ( f ) ( n1 - 1 )) fact = fact1 ( fact1 )
Aquí hay dos operaciones de "aplicar una función de orden superior a sí mismo": 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 ) fact1 = lambda f : ( lambda n1 : 1 if n1 == 0 else n1 * f ( f ) ( n1 - 1 )) fact = C ( fact1 )
Factorizando los otros rendimientos de la doble aplicación:
C = lambda x : x ( x ) D = lambda f : ( lambda x : f ( lambda v : x ( x ) ( v ))) fact1 = lambda g : ( lambda n1 : 1 if n1 == 0 else n1 * g ( n1 - 1 )) hecho = C ( D ( hecho1 ))
La combinación de los dos combinadores en uno produce 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 )) fact1 = lambda g : ( lambda n1 : 1 si n1 == 0 si no n1 * g ( n1 - 1 )) hecho = Y ( hecho1 )
Al expandir el combinador Y se obtiene:
Y = lambda f : ( lambda x : f ( lambda v : x ( x ) ( v ))) \ ( lambda x : f ( lambda v : x ( x ) ( v ))) fact1 = lambda g : ( lambda n1 : 1 si n1 == 0 si no 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 en caso contrario n1 * g ( n1 - 1 )))
Ejemplos de
APL
En APL , se puede acceder al dfn actual a través de ∇
. Esto permite la recursividad 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
JavaScript
En JavaScript , se puede acceder a la función actual mediante arguments.callee
, mientras que se puede acceder a la función de llamada mediante arguments.caller
. Estos permiten la recursividad 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 ; });
Perl
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 undef
fuera de una subrutina. [7] Esto permite la recursividad anónima, como en la siguiente implementación del factorial:
#! / usr / bin / perl usa la función ": 5.16" ;imprimir sub { mi $ x = turno ; $ x > 0 ? $ x * __SUB__ -> ( $ x - 1 ) : 1 ; } -> ( 5 ), "\ n" ;
R
En R , la función actual se puede llamar usando Recall
. Por ejemplo,
sapply ( 0 : 5 , function ( n ) { if ( n == 0 ) return ( 1 ) n * Recall ( 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 cuadra una lista de forma recursiva:
( function ( x ) { if ( is.list ( x )) { lapply ( x , sys.function ( 0 )) } else { x ^ 2 } }) ( list ( list ( 1 , 2 , 3 ), list ( 4 , 5 )))
Referencias
- ^ Problema 226: Es imposible recurrir a una función anónima en Go sin soluciones alternativas.
- ^ a b respuesta de olliej, 25 de octubre de 2008 a " ¿Por qué la propiedad argumentos.callee.caller fue obsoleta en JavaScript? ", StackOverflow
- ^ Esta terminología parece ser en gran parte folklore , pero aparece en lo siguiente:
- Trey Nash, Accelerated C # 2008 , Apress, 2007, ISBN 1-59059-873-3 , pág. 462—463. Derivado sustancialmente del blog de Wes Dyer (ver siguiente artículo).
- Wes Dyer Anonymous Recursion en C # , 02 de febrero de 2007, contiene un ejemplo sustancialmente similar que se encuentra en el libro anterior, pero acompañado de más discusión.
- ↑ The If Works Deriving the Y combinator , 10 de enero de 2008
- ^ La respuesta de Hugo Walter a " ¿Puede una función lambda llamarse a sí misma de forma recursiva en Python? "
- ^ La respuesta de Nux a " ¿Puede una función lambda llamarse a sí misma de forma recursiva en Python? "
- ^ Perldoc, " La característica 'current_sub' ", característica de perldoc
- ^ La respuesta de agstudy a Get Actualmente llama la función de escribir función recursiva anónima en StackOverflow