Как сделать рекурсию в анонимном fn, без хвостовой рекурсии

Как выполнить рекурсию в анонимной функции без использования хвостовой рекурсии?

Например (из Vanderhart 2010, стр. 38):

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

Скажем, я хотел сделать это как анонимную функцию. И по какой-то причине я не хотел использовать хвостовую рекурсию. Как мне это сделать? Например:

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

Могу ли я использовать цикл для этого или цикл может использоваться только с recur?

Ответ 1

Специальная форма 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.

Ответ 2

Я знаю, что в 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

Ответ 3

fn принимает необязательный аргумент имени, который может быть использован для вызова функции рекурсивно.

например:.

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

Ответ 4

Да, вы можете использовать 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

Ответ 5

loop может быть повторной целью, поэтому вы можете сделать это и с этим.