4

我在 Clojure 中定义了以下函数。

; return the input unchanged
(defn same [x] x)

; Recursively call the function on the input N times
(defn recurse-n-times [input function n]
  (if (= n 0)
    input
    (recurse-n-times (function input) function (- n 1))
  )
)

以下是我的递归函数的一些输出：

(recurse-n-times 0 inc 5)     ; returns 5, as expected
(recurse-n-times 0 same 5)    ; returns 0, as expected
(recurse-n-times 0 same 5000) ; StackOverflowError:
                              ; clojure.lang.Numbers$LongOps.combine
                              ; (Numbers.java:394)

我不明白为什么我得到一个StackOverflowError. 最后一件事recurse-n-times是调用自身，所以我希望它使用尾递归并且根本不增加堆栈。

我希望这个替代定义给出StackOverflowError：

(defn bad-recurse-n-times [input function n]
  (if (= n 0)
    input
    (function (alt-recurse-n-times input function (- n 1)))
  )
)

为什么不recurse-n-times使用尾递归？

4

2 回答 2

14

这是 JVM 的限制，而不是 Clojure 的限制。JVM 不支持 TCO。

Clojure 为此提供了一个特殊的形式，recur

(defn recurse-n-times [input function n]
  (if (= n 0)
  input
  (recur (function input) function (- n 1))))

(recurse-n-times 0 same 500000) ;; will work

recur 形式应该出现在尾部位置，否则 Clojure 编译器会抱怨它。

请注意，recur 是 Clojure 中唯一不消耗堆栈的循环结构。没有尾调用优化，不鼓励使用自调用来循环未知边界。recur 是功能性的，它在尾部位置的使用由编译器验证。

于 2013-09-07T22:02:49.730 回答
4

根据clojure.org

没有尾调用优化，使用 recur。

所以你必须使用“recur”特殊形式来做到这一点。

于 2013-09-07T22:01:38.620 回答