Wie Rekursion in anonymer Fn, ohne Tail-Rekursion zu tun

Question

Wie mache ich Rekursion in einer anonymen Funktion, ohne Tail-Rekursion zu verwenden?

Zum Beispiel (von Vanderhart 2010, S. 38):

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

Sagen wir, ich dies als eine anonyme Funktion tun wollte. Und aus irgendeinem Grund wollte ich keine Schwanzrekursion verwenden. Wie würde ich es tun? Zum Beispiel:

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

Kann ich Schleife für diesen, oder Schleife nur mit wiederholt verwendet werden?

Answer 1

die fn besondere Form gibt Ihnen die option to provide a name, die intern für Rekursion verwendet werden kann.

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

Fügen Sie "power" als Namen hinzu, um Ihr Beispiel zu vervollständigen.

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

Auch wenn die Rekursion in der Endposition stattfand, wird sie nicht optimiert, um den aktuellen Stapelrahmen zu ersetzen. Clojure erzwingt, dass Sie mit loop/recur und trampoline explizit darüber sein.

Answer 2

Ich weiß, dass es in Clojure syntaktische Unterstützung für das "Benennen" einer anonymen Funktion gibt, wie andere Antworten darauf hingewiesen haben. Ich möchte jedoch einen First-Principles-Ansatz zur Lösung der Frage zeigen, der nicht von der Existenz einer speziellen Syntax in der Programmiersprache abhängt und der in jeder Sprache mit Prozeduren erster Ordnung (lambdas) funktionieren würde.

Grundsätzlich, wenn Sie eine rekursive Funktionsaufruf tun möchten, müssen Sie den Namen der Funktion verweisen, so „anonymous“ (dh namenlos Funktionen) kann nicht zur Durchführung einer Rekursion verwendet werden, es sei denn ... Sie verwenden die Y-Combinator. Here ist eine Erklärung, wie es in Clojure funktioniert.

Lassen Sie mich Ihnen zeigen, wie es mit einem Beispiel verwendet wird. Zunächst wird ein Y-Combinator, das funktioniert für Funktionen mit einer variablen Anzahl von Argumenten:

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

nun die anonymen Funktion, die die power Prozedur implementiert, wie in der Frage definiert. Klar, es keinen Namen hat, power ist nur ein Parameter an die äußersten Funktion:

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

Schließlich ist hier, wie die Y-Combinator die anonymen power Verfahren anzuwenden, als Parameter übergeben number=5 und exponent=3 (es ist nicht tail-rekursive BTW):

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

> 125 

Answer 3

fn nimmt eine optional name argument, die verwendet werden kann, um die Funktion rekursiv aufzurufen.

z.:

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

Answer 4

Ja, Sie können dafür loop verwenden. recur Arbeiten in beiden loop s und fn s

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

eine idomatic clojure Lösung sieht wie folgt aus:

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

oder verwendet Math.pow() ;-)

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

Answer 5

loop können sei ein wiederkehrendes Ziel, also könntest du es auch tun.