recursion - recursivas - recursividad en programacion

En Esquema, ¿cómo usas lambda para crear una función recursiva?

Question

Estoy en una clase de Scheme y tenía curiosidad por escribir una función recursiva sin usar define. El principal problema, por supuesto, es que no puede llamar una función dentro de sí misma si no tiene un nombre.

Encontré este ejemplo: es un generador factorial que usa solo lambda.

((lambda (x) (x x))
 (lambda (fact-gen)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((fact-gen fact-gen) (sub1 n)))))))

Pero ni siquiera puedo entender la primera llamada, (lambda (x) (xx)): ¿Qué hace exactamente eso? ¿Y dónde ingresa el valor del cual desea obtener el factorial?

Esto no es para la clase, esto es solo por curiosidad.

Answer 1

Tenía curiosidad por escribir una función recursiva sin usar definir. El principal problema, por supuesto, es que no puede llamar una función dentro de sí misma si no tiene un nombre.

Un poco fuera de tema aquí, pero viendo las afirmaciones anteriores, solo quería hacerle saber que "sin usar define" no significa "no tiene nombre". Es posible dar un nombre a algo y usarlo recursivamente en Esquema sin definir.

(letrec
  ((fact
     (lambda (n)
       (if (zero? n)
         1
         (* n (fact (sub1 n)))))))
  (fact 5))

Sería más claro si su pregunta dice específicamente "recursión anónima".

Answer 2

Básicamente, lo que tienes es una forma similar al combinador Y. Si reformula el código factorial específico para que se pueda implementar cualquier función recursiva, entonces el código restante sería el combinador Y.

Yo mismo he pasado por estos pasos para una mejor comprensión.
https://gist.github.com/z5h/238891

Si no te gusta lo que he escrito, haz un poco de google para Y Combinator (la función).

Answer 3

La expresión (lambda (x) (xx)) crea una función que, cuando se evalúa con un argumento (que debe ser una función), aplica esa función consigo misma como un argumento.

La expresión dada se evalúa como una función que toma un argumento numérico y devuelve el factorial de ese argumento. Intentarlo:

(let ((factorial ((lambda (x) (x x))
                  (lambda (fact-gen)
                    (lambda (n)
                      (if (zero? n)
                          1
                          (* n ((fact-gen fact-gen) (sub1 n)))))))))
  (display (factorial 5)))

Hay varias capas en su ejemplo, vale la pena trabajar paso a paso y examinar cuidadosamente lo que hace cada una.

Answer 4

Lo definas así:

(let ((fact #f)) 
  (set! fact 
        (lambda (n) (if (< n 2) 1 
                               (* n (fact (- n 1)))))) 
  (fact 5))

que es como letrec realmente letrec . Ver LiSP por Christian Queinnec.

En el ejemplo sobre el que está preguntando, el combinador de autoaplicación se llama " U combinator" ,

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
  ((U h) 5))

La sutileza aquí es que, debido let las reglas de alcance de Let, las expresiones lambda no pueden referirse a los nombres que se están definiendo.

Cuando se llama ((U h) 5) , se reduce a ((hh) 5) aplicación, dentro del marco de entorno creado por la forma let .

Ahora, la aplicación de h to h crea un nuevo marco de entorno en el que g apunta a h en el entorno que está por encima de él:

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
  ( (let ((g h))
      (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n)))))) 
    5))

La expresión (lambda (n) ...) aquí se devuelve desde ese marco de entorno en el que g apunta a h sobre ella, como un objeto de cierre . Es decir, una función de un argumento, n , que también recuerda los enlaces de g , h y U

Entonces, cuando se llama a este cierre, a n se le asigna 5 , y se ingresa el formulario if :

(let ((U  (lambda (x) (x x)))
      (h  (lambda (g)
            (lambda (n)
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n))))))))
    (let ((g h))
      (let ((n 5))
              (if (zero? n)
                  1
                  (* n ((g g) (sub1 n)))))))

La aplicación (gg) se reduce a (hh) porque g apunta a h definida en el marco del entorno sobre el entorno en el que se creó el objeto de cierre. Lo que quiere decir, allá arriba, en la parte superior de forma. Pero ya hemos visto la reducción de (hh) call, que creó el cierre, es decir, la función de un argumento n , que sirve como nuestra función factorial , que en la siguiente iteración se llamará con 4 , luego 3 etc.

Si será un nuevo objeto de cierre o el mismo objeto de cierre se reutilizará, depende de un compilador. Esto puede tener un impacto en el rendimiento, pero no en la semántica de la recursión.

Answer 5

Me gusta esta pregunta. ''El lenguaje de programación del esquema'' es un buen libro. Mi idea es del capítulo 2 de ese libro.

Primero, sabemos esto:

(letrec ((fact (lambda (n) (if (= n 1) 1 (* (fact (- n 1)) n))))) (fact 5))

Con letrec podemos realizar funciones recursivamente. Y vemos que cuando llamamos (fact 5) , el fact ya está vinculado a una función. Si tenemos otra función, podemos llamarlo de esta manera (another fact 5) , y ahora a another se le llama función binaria (mi inglés no es bueno, lo siento). Podemos definir another como este:

(let ((another (lambda (f x) .... (f x) ...))) (another fact 5))

¿Por qué no definimos el fact esta manera?

(let ((fact (lambda (f n) (if (= n 1) 1 (* n (f f (- n 1))))))) (fact fact 5))

Si fact es una función binaria , puede llamarse con una función f y un entero n , en cuyo caso la función f pasa a ser fact sí misma.

Si tienes todo lo anterior, puedes escribir Y combinator ahora, haciendo una sustitución de let con lambda .

Answer 6

(lambda (x) (xx)) es una función que invoca un argumento, x , sobre sí mismo.

Todo el bloque de código que publicó resulta en una función de un argumento. Podrías llamarlo así:

(((lambda (x) (x x))
  (lambda (fact-gen)
    (lambda (n)
      (if (zero? n)
          1
          (* n ((fact-gen fact-gen) (sub1 n)))))))
 5)

Eso lo llama con 5, y devuelve 120.

La forma más fácil de pensar esto en un nivel alto es que la primera función, (lambda (x) (xx)) , le está dando a x una referencia a sí misma, de modo que ahora x puede referirse a sí misma, y ​​por lo tanto recursionar.

Answer 7

(lambda (x) (xx)) toma un objeto de función, luego invoca ese objeto usando un argumento, el objeto de función en sí.

Luego se llama a esta función con otra función, que toma ese objeto de función con el nombre de parámetro fact-gen . Devuelve un lambda que toma el argumento real, n . Así es como funciona ((fact-gen fact-gen) (sub1 n)) .

Debes leer el capítulo de muestra (Capítulo 9) de The Little Schemer si puedes seguirlo. Describe cómo construir funciones de este tipo y, en última instancia, extraer este patrón en el combinador de Y (que se puede usar para proporcionar recursión en general).