如何在无尾递归的fn中进行递归

How do I do recursion in an anonymous function, without using tail recursion?

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

For example (from Vanderhart 2010, p 38):

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

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

Let's say I wanted to do this as an anonymous function. And for some reason I didn't want to use tail recursion. How would I do it? For example:

假设我想做一个匿名函数。出于某种原因，我不想使用尾部递归。我该怎么做呢?例如:

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

Can I use loop for this, or can loop only be used with recur?

我可以用循环来做这个，还是只能用循环来做循环?

5 个解决方案

#1

The fn special form gives you the option to provide a name that can be used internally for recursion.

fn特殊表单提供了提供一个名称的选项，该名称可以在内部用于递归。

(doc fn)
;=> (fn name? [params*] exprs*)

So, add "power" as the name to complete your example.

因此，添加“power”作为完成示例的名称。

(fn power [n e]
  (if (zero? e)
    1
    (* n (power n (dec e)))))

Even if the recursion happened in the tail position, it will not be optimized to replace the current stack frame. Clojure enforces you to be explicit about it with loop/recur and trampoline.

即使递归发生在尾部位置，也不会对其进行优化以替换当前堆栈帧。Clojure强制您使用循环/重复和蹦床对其进行明确说明。

#2

I know that in Clojure there's syntactic support for "naming" an anonymous function, as other answers have pointed out. However, I want to show a first-principles approach to solve the question, one that does not depend on the existence of special syntax on the programming language and that would work on any language with first-order procedures (lambdas).

我知道在Clojure中，语法支持“命名”匿名函数，其他答案也指出了这一点。但是，我想展示一种解决问题的第一原则方法，这种方法不依赖于编程语言中特殊语法的存在，并且可以在任何具有一阶过程(lambdas)的语言上工作。

In principle, if you want to do a recursive function call, you need to refer to the name of the function so "anonymous" (i.e. nameless functions) can not be used for performing a recursion ... unless you use the Y-Combinator. Here's an explanation of how it works in Clojure.

原则上，如果要执行递归函数调用，则需要引用函数的名称，因此不能使用“匿名”(即匿名函数)来执行递归。除非你用Y-Combinator。这里有一个关于它在Clojure中的工作原理的解释。

Let me show you how it's used with an example. First, a Y-Combinator that works for functions with a variable number of arguments:

让我用一个例子来说明它是如何使用的。首先，一个y组合子，用于参数数目可变的函数:

(defn Y [f]
  ((fn [x] (x x))
   (fn [x]
       (f (fn [& args]
              (apply (x x) args))))))

Now, the anonymous function that implements the power procedure as defined in the question. Clearly, it doesn't have a name, power is only a parameter to the outermost function:

现在，匿名函数实现了问题中定义的power过程。显然，它没有名字，功率只是最外层函数的一个参数:

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

Finally, here's how to apply the Y-Combinator to the anonymous power procedure, passing as parameters number=5 and exponent=3 (it's not tail-recursive BTW):

最后，如何将Y-Combinator应用到匿名幂函数过程中，传递为参数数=5，指数=3(这不是尾部递归):

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

> 125

#3

fn takes an optional name argument that can be used to call the function recursively.

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

E.g.:

例如:

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

#4

Yes you can use loop for this. recur works in both loops and fns

是的，你可以用循环。recur在循环和fns中都起作用

user> (loop [result 5 x 1] (if (= x 3) result (recur (* result 5) (inc x))))
125

an idomatic clojure solution looks like this:

类似的clojure解决方案如下:

user> (reduce * (take 3 (repeat 5)))
125

or uses Math.pow() ;-)

或使用Math.pow();-)

user> (java.lang.Math/pow 5 3)
125.0

#5

loop can be a recur target, so you could do it with that too.

循环可以是一个循环目标，所以你也可以这样做。

#1