Recursión anónima

La alternativa habitual es usar funciones con nombre y recursión con nombre. Dada una función anónima, esto se puede hacer asignando 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 sentencias 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 referirse a la función en sí y rechazan explícitamente la recursión anónima; ejemplos de ello son 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 usar una expresión de función con nombre produce:

[ 1 , 2 , 3 , 4 , 5 ]. map ( function factorial ( n ) { return ( ! ( n > 1 )) ? 1 : factorial ( n - 1 ) * n ; });

Incluso sin mecanismos para referirse a la función actual o a la función que realiza la llamada, la recursión anónima es posible en un lenguaje que permite funciones como argumentos. Esto se logra 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 al pasar esta función superior se permite la recursión anónima dentro de la función recursiva propiamente dicha. Esto se puede hacer de forma completamente 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 compleja que la función recursiva original con nombre. 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 ]}

Esto se ilustra a continuación usando Python . Primero, una recursión con nombre estándar:

def fact ( n ): if n == 0 : return 1 return n * fact ( n - 1 )

Utilizar una función de orden superior para que la función de nivel superior recurse de forma anónima sobre un argumento, pero aún necesitando 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 : fact1 ( fact0 , n )

Podemos eliminar la función recursiva estándar pasando el argumento de la función a la llamada:

fact1 = lambda f , n1 : 1 si n1 == 0 sino n1 * f ( f , n1 - 1 ) fact = lambda n : fact1 ( fact1 , n )

La segunda línea puede ser reemplazada 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 anónimamente: ^{[ 5 ]}

( lambda f : ( lambda x : f ( f , x ))) \ ( lambda g , n1 : 1 if n1 == 0 else n1 * g ( g , n1 - 1 ))

En el cálculo lambda , que solo utiliza funciones de una sola variable, esto se puede hacer mediante el 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 currificación :

hecho1 = lambda f : ( lambda n1 : 1 si n1 == 0 sino n1 * f ( f )( n1 - 1 )) hecho = hecho1 ( hecho1 )

Aquí hay dos operaciones de "aplicar 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 , obtenemos:

C = lambda x : x ( x ) fact1 = lambda f : ( lambda n1 : 1 if n1 == 0 else n1 * f ( f )( n1 - 1 )) fact = C ( fact1 )

Al factorizar la otra doble aplicación se obtiene:

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 )) fact = C ( D ( fact1 ))

La combinación de los dos combinadores en uno solo da como resultado 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 if n1 == 0 else n1 * g ( n1 - 1 )) fact = Y ( fact1 )

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 if n1 == 0 else n1 * g ( n1 - 1 )) fact = Y ( fact1 )

La combinación de estos elementos 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 if n1 == 0 else n1 * g ( n1 - 1 )))

En APL , la función dinámica actual es accesible 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. Esto permite 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 mediante el __SUB__token, que devuelve una referencia a la subrutina actual, o undefdesde fuera de una subrutina. ^{[ 7 ]} Esto permite la recursión anónima, como en la siguiente implementación del factorial:

#!/usr/bin/env perl use feature ":5.16" ;print sub { my $x = shift ; $x > 0 ? $x * __SUB__ -> ( $x - 1 ) : 1 ; } -> ( 5 ), "\n" ;

En R , la función actual se puede llamar usando Recall. Por ejemplo,

aplicar ( 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 la función anónima. En este caso, sys.function(0)se puede usar. ^{[ 8 ]} Por ejemplo, el siguiente código eleva al cuadrado una lista recursivamente:

( función ( x ) { si ( es.lista ( x )) { aplicar ( x , sys.función ( 0 )) } de lo contrario { x ^ 2 } })( lista ( lista ( 1 , 2 , 3 ), lista ( 4 , 5 )))