如何在匿名fn中进行递归,没有尾递归

Question

如何在不使用尾递归的情况下在匿名函数中进行递归？

例如(来自Vanderhart 2010,第38页):

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

假设我想将其作为匿名函数执行此操作.由于某种原因,我不想使用尾递归.我该怎么办？例如:

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

我可以使用循环这一点,也可以仅环搭配使用易复发？

Answer 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.

Answer 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(它不是尾递归BTW):

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

> 125