如何在匿名函数中进行递归，而不使用尾递归

Question

如何在匿名函数中进行递归，而不使用尾递归？

例如（摘自 Vanderhart 2010 年第38页）：

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

假设我想将这个函数写成匿名函数的形式，并且出于某种原因我不想使用尾递归。我该如何做呢？例如：

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

我可以使用loop吗，还是只能与recur一起使用？

- Sonia Hamilton

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来解决这个问题。

- Jeremy

---

谢谢Jeremy，我不知道有name选项。我正在解决4clojure的问题，他们不允许defn。尾递归显然更好，但我想先学会基础再深入 :) - Sonia Hamilton

Answer 2

我知道在Clojure中有语法支持“命名”匿名函数，正如其他答案所指出的那样。然而，我想展示一种基于原则的方法来解决问题，这种方法不依赖于编程语言上的特殊语法，并且可以在任何具有一阶过程（lambda）的语言中使用。

原则上，如果您想进行递归函数调用，您需要引用函数的名称，因此“匿名”（即无名称）函数不能用于执行递归...除非您使用Y-组合器。这里是如何在Clojure中使用它的解释。

让我用一个例子来向您展示它的用法。首先，一个适用于具有可变参数数量的函数的Y-组合器：

(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作为参数传递（顺便说一下，它不是尾递归）：

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

> 125

- Óscar López

---

谢谢，Óscar。Y组合子看起来非常有趣 - 我会更加深入地学习它！ - Sonia Hamilton

理解Y组合子的另一个好资源是《The Little Schemer》（https://mitpress.mit.edu/books/little-schemer）。 - Mars

Answer 3

fn函数可以接受一个可选的名称参数，用于递归调用该函数。

例如：

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

- gregspurrier

---

谢谢Greg，看来使用名称选项是正确的选择。 - Sonia Hamilton

Answer 4

是的，你可以使用loop来实现此功能。在loop和fn中都可以使用recur。

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

- Arthur Ulfeldt

---

但问题是“不使用尾递归” :-) - Sonia Hamilton

Answer 5

loop可以作为一个递归目标，所以你也可以用它来实现。

- BillRobertson42

---

但问题是“不使用尾递归” :-) - Sonia Hamilton

我知道，但是recur并不执行递归，编译器会为你修复一个循环（即使在尾递归的情况下）。所以有点不一样。 - BillRobertson42