尾递归函数不也应该更快吗？

Question

我使用下面的Clojure代码来计算具有某个"factorable“属性的数字。(代码到底做什么是次要的)。

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (factor-9 (quot n 10))))))

现在，我已经了解了总体拥有成本，并且意识到Clojure只能在使用recur关键字显式指定的情况下提供尾递归。所以我重写了代码来做到这一点(用recur替换factor-9是唯一的区别)：

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (recur (quot n 10))))))

据我所知，TCO有双重好处。第一个是它不像非尾递归调用那样大量使用堆栈，因此不会在较大的递归中破坏堆栈。第二，我认为，由于它可以转换为循环，因此它更快。

现在，我已经做了一个非常粗略的基准测试，虽然没有看到两种实现之间的任何差异。我的第二个假设是不是错了，或者这与在JVM (没有自动总体拥有成本)和recur上运行有什么关系？

谢谢。

Answer 1

使用recur确实加快了速度，但比递归调用只提高了大约3纳秒(实际上)。当事情变得那么小时，它们可能会隐藏在测试的其余部分的噪音中。我写了四个测试(下面的链接)，它们能够说明性能上的差异。

我还建议在进行基准测试时使用criterium之类的东西。(堆栈溢出不允许我发布超过1个链接，因为我没有声誉可言，所以你必须搜索它，也许是"clojure criterium")

出于格式化的原因，我将测试和结果放在这个gist中。

简而言之，相对而言，如果递归测试为1，则循环测试约为0.45，TCO测试约为0.87，递归测试与TCO测试之间的绝对差异约为3 3ns。

当然，关于基准测试的所有警告都适用。

Answer 2

在优化任何代码时，最好从潜在或实际的瓶颈开始，并首先对其进行优化。

在我看来，这段特定的代码占用了你大部分的CPU时间：

 (map (fn [x] ,(Integer. (apply str x))) (permutations digits))

而且这并不以任何方式依赖于TCO -它是以相同的方式执行的。因此，在这个特定的示例中，尾部调用将允许您不会耗尽所有堆栈，但为了获得更好的性能，请尝试对其进行优化。

Answer 3

只是一个异教徒的提醒，clojure没有TCO