Cómo hacer la recursión en anonymous fn, sin repetición de cola

¿Cómo hago la recursión en una función anónima, sin usar la recursividad de cola?Cómo hacer la recursión en anonymous fn, sin repetición de cola

Por ejemplo (de Vanderhart 2010, p 38):

(defn power 
    [number exponent] 
    (if (zero? exponent) 
    1 
    (* number (power number (- exponent 1)))))

Digamos que quería hacer esto como una función anónima. Y por alguna razón no quería usar la recursividad de cola. ¿Cómo lo haría? Por ejemplo:

((fn [number exponent] ......))))) 5 3) 
125

¿Puedo usar bucle para esto, o puede ser utilizado en bucle con reaparecer?

Fuente

2012-05-07 Sonia Hamilton

la forma especial fn le da la option to provide a name que puede ser utilizado internamente para la recursividad.

(doc fn) 
;=> (fn name? [params*] exprs*)

Por lo tanto, agregue "potencia" como el nombre para completar su ejemplo.

(fn power [n e] 
    (if (zero? e) 
    1 
    (* n (power n (dec e)))))

Incluso si la recursión ocurrió en la posición de cola, no se optimizará para reemplazar el marco de pila actual. Clojure lo obliga a ser explícito con loop/recur y trampoline.

Fuente

2012-05-07 23:57:54 Jeremy

Gracias Jeremy, no sabía sobre la opción de nombre. Estoy trabajando en las preguntas [4clojure] (http://www.4clojure.com/) y no permiten defn. La recurrencia de la cola es obviamente mejor, pero quiero caminar antes de correr :) –

Sé que en Clojure hay soporte sintáctico para "nombrar" una función anónima, como han señalado otras respuestas. Sin embargo, quiero mostrar un enfoque de primeros principios para resolver la pregunta, uno que no dependa de la existencia de una sintaxis especial en el lenguaje de programación y que funcionaría en cualquier idioma con procedimientos de primer orden (lambdas).

En principio, si usted quiere hacer una llamada de función recursiva, es necesario hacer referencia al nombre de la función tan "anónimo" (es decir, sin nombre funciones) no se pueden utilizar para realizar una recursión ... a menos usa el Y-Combinator. Here es una explicación de cómo funciona en Clojure.

Déjame mostrarte cómo se usa con un ejemplo. En primer lugar, un Y-Combinator que funcione para las funciones con un número variable de argumentos:

(defn Y [f] 
    ((fn [x] (x x)) 
    (fn [x] 
     (f (fn [& args] 
       (apply (x x) args))))))

Ahora, el anónima función que implementa el procedimiento power como se define en la pregunta. Está claro que no tiene un nombre, power sólo es un parámetro a la función externa:

(fn [power] 
     (fn [number exponent] 
      (if (zero? exponent) 
       1 
       (* number (power number (- exponent 1))))))

Por último, aquí es cómo aplicar el Y-Combinator al procedimiento anónima power, pasando como parámetros number=5 y exponent=3 (que no es recursiva de cola por cierto):

((Y 
    (fn [power] 
     (fn [number exponent] 
      (if (zero? exponent) 
       1 
       (* number (power number (- exponent 1))))))) 
5 3) 

> 125

Fuente

2012-05-07 23:40:24

Gracias Óscar. El Y-Combinator se ve muy interesante, ¡voy a estudiarlo más! –

Otra buena fuente para entender el combinador Y es [The Little Schemer] (https://mitpress.mit.edu/books/little-schemer). – Mars

fn toma un optional name argument que se puede utilizar para llamar a la función recursivamente.

E.g.:

user> ((fn fact [x] 
      (if (= x 0) 
       1 
       (* x (fact (dec x))))) 
     5) 
;; ==> 120

Fuente

2012-05-08 00:00:51 gregspurrier

Gracias Greg, parece que la opción de nombre es el camino a seguir. –

Sí, puede usar loop para esto. recur obras en ambos loop s y

user> (loop [result 5 x 1] (if (= x 3) result (recur (* result 5) (inc x)))) 
125

una solución clojure idiomáticas fn s

se parece a esto:

user> (reduce * (take 3 (repeat 5))) 
125

o utiliza Math.pow() ;-)

user> (java.lang.Math/pow 5 3) 
125.0

Fuente

2012-05-08 01:02:40

Pero la pregunta era "sin hacer repetición de cola" :-) –

loop puede ser un objetivo recurrente, por lo que podría hacerlo con eso también.

Fuente

2012-05-08 01:02:52 Bill

Pero la pregunta era "sin hacer repetición de cola" :-) –

:-) Lo sé, pero recurre no hace recursividad, el compilador corregirá un bucle para usted (incluso en la situación de recursividad de cola). Así que no. – Bill

Cómo hacer la recursión en anonymous fn, sin repetición de cola

Respuesta

Cuestiones relacionadas