21

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

例如（来自 Vanderhart 2010，第 38 页）：

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

假设我想将其作为匿名函数来执行。出于某种原因，我不想使用尾递归。我该怎么做？例如：

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

我可以为此使用循环，还是循环只能与recur一起使用？

4

5 回答 5

47

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。

于 2012-05-07T23:57:54.230 回答
18

我知道在 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
于 2012-05-07T23:40:24.667 回答
4

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

例如：

user> ((fn fact [x]
           (if (= x 0)
               1
               (* x (fact (dec x)))))
       5)
;; ==> 120
于 2012-05-08T00:00:51.903 回答
3

是的，您可以使用loop它。recur适用于loops 和fns

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
于 2012-05-08T01:02:40.610 回答
0

循环可以是重复目标，所以你也可以这样做。

于 2012-05-08T01:02:52.160 回答