我做错了什么?简单的递归调用几千次会抛出 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)
我做错了什么?简单的递归调用几千次会抛出 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)
以下是另一种方法:
(defn factorial [n]
(reduce * (range 1 (inc n))))
由于range
返回一个惰性序列,而reduce
在不保留头部的情况下遍历整个序列,所以这个程序不会导致堆栈溢出。
reduce
会尽可能地使用分块序列,因此它实际上可以比手动使用recur
更高效。与Siddhartha Reddy的基于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
和其他更易读和明确的函数,并且更优雅地在内部使用recur
,而不是手动编写。根据我的经验,需要手动使用recur
的时候并不多。
我理解堆栈大小取决于你使用的JVM以及平台。如果你使用Sun JVM,可以使用-Xss
和-XThreadStackSize
参数来设置堆栈大小。
然而,在Clojure中执行递归的首选方法是使用loop
/recur
:
(defn fact [x]
(loop [n x f 1]
(if (= n 1)
f
(recur (dec n) (* f n)))))
Clojure会对此进行尾递归优化,这可以确保您永远不会遇到StackOverflowError
。
由于defn
意味着一个loop
绑定,因此可以省略loop
表达式,并将其参数用作函数参数。要将其作为一个一元函数使用,请使用函数的多元特性:
(defn fact
([n] (fact n 1))
([n f]
(if (<= n 1)
f
(recur (dec n) (* f n)))))
编辑:为了记录,这里是一个Clojure函数,它返回所有阶乘的惰性序列:
(defn factorials []
(letfn [(factorial-seq [n fact]
(lazy-seq
(cons fact (factorial-seq (inc n) (* (inc n) fact)))))]
(factorial-seq 1 1)))
(take 5 (factorials)) ; will return (1 2 6 24 120)
(def facts (lazy-cat [1] (map * facts (iterate inc 2))))
。然后 (take 5 facts)
会产生 (1 2 6 24 120)
。 - Alexei Sholik(def facts (reductions * (iterate inc 1)))
。 这段代码定义了一个名为"facts"的变量,它使用了两个函数:iterate
和 reductions
。其中,iterate
函数生成一个从1开始的无限长整数序列,并递增1。reductions
函数则将这个整数序列依次传递给 *
运算符进行累乘,得到一个新的序列作为结果存储在 facts
变量中。 - rhuClojure 有多种方法可以避免递归
(defn fact ([x] (trampoline (fact (dec x) x)))
([x a] (if (<= x 1) a #(fact (dec x) (*' x a)))))
(fact 42)
620448401733239439360000N
附注:我手头没有REPL,所以有没有人能够善意地测试和修复trapoline fact函数?
(defn fact ([x] (fact x nil)) ([ x lastResult] (if (<= x 1) (if (nil? lastResult) 1 lastResult) (if (nil? lastResult) (fact (dec x) x) (fact (dec x) (* lastResult x ))) )) )
。另外,trampoline是使用(trampoline fn arg)调用的,因此应该删除(fact 42)周围的括号。 - Kevin Zhu我准备发布以下内容时,发现与JasonTrue发布的Scheme示例几乎相同...不管怎样,这是Clojure中的一种实现:
user=> (defn fact[x]
((fn [n so_far]
(if (<= n 1)
so_far
(recur (dec n) (* so_far n)))) x 1))
#'user/fact
user=> (fact 0)
1
user=> (fact 1)
1
user=> (fact 2)
2
user=> (fact 3)
6
user=> (fact 4)
24
user=> (fact 5)
120
etc.
堆栈深度是一个小烦恼(但可配置),但即使在具有尾递归的语言(如Scheme或F#)中,您最终也会用完代码的堆栈空间。
据我所知,即使在支持透明尾递归的环境中,您的代码也不太可能进行尾递归优化。您需要查看延续传递样式以最小化堆栈深度。
这里是来自Wikipedia的Scheme中的经典示例,可以轻松转换为Clojure、F#或其他函数式语言:
(define factorial
(lambda (n)
(let fact ([i n] [acc 1])
(if (zero? i)
acc
(fact (- i 1) (* acc i))))))
(defn fac [n]
((fn [product counter max-count]
(if (> counter max-count)
product
(recur (apply *' [counter product])
(inc counter)
max-count)))
1 1 n))
另一个简单的递归实现可能是这样的:
(defn fac [x]
"Returns the factorial of x"
(if-not (zero? x) (* x (fac (- x 1))) 1))
阶乘数由于其本质的巨大性质而变得非常大。我不确定Clojure如何处理这个问题(但我确实看到它与java一起工作),但是任何不使用大数的实现都会非常快地溢出。
编辑:这还没有考虑到您正在使用递归,这也很可能会耗尽资源。
编辑x2:如果实现使用大数,通常是数组,再加上递归(每个函数入口一个大数副本,由于函数调用始终保存在堆栈上),这将解释为什么会发生堆栈溢出。尝试在for循环中执行以查看是否存在该问题。
;; Clojure 1.5.0-beta2 => (fact 400) ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)
- m0skit0*'
而不是 *
,它不会在溢出时抛出异常,而是动态地使用所需的类型。 - m0skit0
(defn 阶乘 [n] (apply * (range 1 (inc n))))
- miguelv(defn factorial [n] (reduce *' (range 1 (inc n))))
注意*符号旁边的 ' 标记。 - Danny Armstrong