Come fare la ricorsione in fn anonima, senza ricorsione in coda

Question

Come si fa la ricorsione in una funzione anonima, senza ricorrere alla ricorsione in coda?

Per esempio (da Vanderhart 2010, p 38):

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

Diciamo che ho voluto fare questo come una funzione anonima. E per qualche motivo non volevo usare la ricorsione della coda. Come lo farei? Per esempio:

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

Posso usare ciclo per questo, o ciclo essere utilizzato solo con può ripresentarsi?

Answer 1

il fn forma particolare si dà la option to provide a name che può essere utilizzato internamente per la ricorsione.

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

Quindi, aggiungere "potere" come nome per completare il vostro esempio.

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

Anche se la ricorsione successo nella posizione coda, non sarà ottimizzato per sostituire stack frame corrente. Clojure ti impone di essere esplicito al riguardo con loop/recur e trampoline.

Answer 2

So che in Clojure esiste il supporto sintattico per "denominare" una funzione anonima, come hanno sottolineato altre risposte. Tuttavia, voglio mostrare un approccio di primo principio per risolvere la domanda, uno che non dipende dall'esistenza di una sintassi speciale sul linguaggio di programmazione e che funzionerebbe in qualsiasi lingua con procedure di primo ordine (lambda).

In linea di principio, se si vuole fare una chiamata di funzione ricorsiva, è necessario fare riferimento al nome della funzione in modo "anonimo" (vale a dire senza nome funzioni) non possono essere utilizzate per l'esecuzione di una ricorsione ... a meno che non usi lo Y-Combinator. Here è una spiegazione di come funziona in Clojure.

Lascia che ti mostri come viene utilizzato con un esempio. In primo luogo, un Y-Combinator che funziona per le funzioni con un numero variabile di argomenti:

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

Ora, il anonima funzione che implementa la procedura power come definito nella questione. Chiaramente, non ha un nome, power è solamente un parametro alla funzione più esterna:

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

Infine, ecco come applicare il Y-Combinator alla anonima power procedura, passando come parametri number=5 e exponent=3 (non è tail-ricorsiva BTW):

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

> 125 

Answer 3

fn prende uno optional name argument che può essere utilizzato per chiamare la funzione in modo ricorsivo.

E.g.:

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

Answer 4

Sì, è possibile utilizzare loop per questo. recur opere in entrambi loop s e fn s

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

una soluzione clojure idomatic assomiglia a questo:

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

o utilizza Math.pow() ;-)

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

Answer 5

loop può essere un obiettivo ricorrente, quindi potresti farlo anche con quello.