Как выполнить рекурсию в анонимной функции без использования хвостовой рекурсии?
Например (из Vanderhart 2010, стр. 38):
(defn power
[number exponent]
(if (zero? exponent)
1
(* number (power number (- exponent 1)))))
Скажем, я хотел сделать это как анонимную функцию. И по какой-то причине я не хотел использовать хвостовую рекурсию. Как мне это сделать? Например:
( (fn [number exponent] ......))))) 5 3)
125
Могу ли я использовать цикл для этого или цикл может использоваться только с recur?
Специальная форма fn предоставляет параметр для указания имени, который может использоваться внутри для рекурсии.
(doc fn)
;=> (fn name? [params*] exprs*)
Итак, добавьте "power" в качестве имени для завершения вашего примера.
(fn power [n e]
(if (zero? e)
1
(* n (power n (dec e)))))
Даже если рекурсия произошла в позиции хвоста, она не будет оптимизирована для замены текущего кадра стека. Clojure заставляет вас говорить об этом с помощью loop/recur и trampoline.
Я знаю, что в Clojure есть синтаксическая поддержка для "именования" анонимной функции, как указывали другие ответы. Тем не менее, я хочу показать подход первого принципа для решения вопроса, который не зависит от наличия специального синтаксиса на языке программирования и который будет работать на любом языке с процедурами первого порядка (lambdas).
В принципе, если вы хотите выполнить вызов рекурсивной функции, вам нужно обратиться к имени функции, чтобы "анонимные" (например, безымянные функции) не могли использоваться для выполнения рекурсии... если вы не используете Y-Combinator. Здесь объяснение того, как он работает в Clojure.
Позвольте мне показать вам, как он используется с примером. Во-первых, Y-Combinator, который работает для функций с переменным числом аргументов:
(defn Y [f]
((fn [x] (x x))
(fn [x]
(f (fn [& args]
(apply (x x) args))))))
Теперь анонимная функция, которая реализует процедуру power, как определено в вопросе. Очевидно, что у него нет имени, power является только параметром самой внешней функции:
(fn [power]
(fn [number exponent]
(if (zero? exponent)
1
(* number (power number (- exponent 1))))))
Наконец, здесь, как применить процедуру Y-Combinator к анонимной power, передав ее как параметры number=5 и exponent=3 (это не tail-recursive BTW):
((Y
(fn [power]
(fn [number exponent]
(if (zero? exponent)
1
(* number (power number (- exponent 1)))))))
5 3)
> 125
fn принимает необязательный аргумент имени, который может быть использован для вызова функции рекурсивно.
например:.
user> ((fn fact [x]
(if (= x 0)
1
(* x (fact (dec x)))))
5)
;; ==> 120
Да, вы можете использовать loop для этого. recur работает как в loop, так и fn
user> (loop [result 5 x 1] (if (= x 3) result (recur (* result 5) (inc x))))
125
идемное решение clojure выглядит следующим образом:
user> (reduce * (take 3 (repeat 5)))
125
или использует Math.pow(); -)
user> (java.lang.Math/pow 5 3)
125.0
loop может быть повторной целью, поэтому вы можете сделать это и с этим.