recursion - Clojure:简单阶乘导致堆栈溢出

Question

我做错了什么？简单的递归几千次深度调用会引发 StackOverflowError。

如果 Clojure 递归的限制如此之低，我该如何依赖它？

(defn fact[x]
  (if (<= x 1) 1 (* x  (fact (- x 1))  )))

user=> (fact 2)
2

user=> (fact 4)
24

user=> (fact 4000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

Answer 1

这是另一种方法:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

这不会破坏堆栈，因为 range 返回一个惰性 seq，而 reduce 会遍历该 seq 而不会捕获头部。

reduce 如果可以的话，会使用分块的 seq，因此这实际上比您自己使用 recur 的性能更好。使用Siddhartha Reddy's基于 recur 的版本和基于 reduce 的版本:

user> (time (do (factorial-recur 20000) nil))
"Elapsed time: 2905.910426 msecs"
nil
user> (time (do (factorial-reduce 20000) nil))
"Elapsed time: 2647.277182 msecs"
nil

只是有一点点不同。我喜欢将我的 recur 环留给 map 和 reduce 以及 friend ，它们更具可读性和明确性，并使用 recur 内部比我手工做的要优雅一些。有时您需要手动重复，但根据我的经验，次数并不多。