Clojure:简单的阶乘计算导致堆栈溢出

31

我做错了什么?简单的递归调用几千次会抛出 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)
9个回答

77

以下是另一种方法:

(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留给mapreduce和其他更易读和明确的函数,并且更优雅地在内部使用recur,而不是手动编写。根据我的经验,需要手动使用recur的时候并不多。


10
我完全同意。我认为这种方法比直接使用循环/递归更好,即使速度差异不存在也是如此。我个人只会采用这种方法。我主要使用循环/递归版本来演示Clojure中的递归。 - Siddhartha Reddy
我也很喜欢它。顺便说一下,这也可以是:(defn 阶乘 [n] (apply * (range 1 (inc n)))) - miguelv
4
在Clojure 1.3.0中,我编写了以下代码以计算n > 20的阶乘: (defn factorial [n] (reduce *' (range 1 (inc n)))) 注意*符号旁边的 ' 标记。 - Danny Armstrong
@MiguelVitorino 但是你的版本是否保留了头部?想象一下,你的范围放在另一个函数的参数中。 - johnbakers

45

我理解堆栈大小取决于你使用的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
9
@android - 另一种表达相同意思的方式(自Clojure1.3以来):(def facts (reductions * (iterate inc 1)))。 这段代码定义了一个名为"facts"的变量,它使用了两个函数:iteratereductions。其中,iterate 函数生成一个从1开始的无限长整数序列,并递增1。reductions 函数则将这个整数序列依次传递给 * 运算符进行累乘,得到一个新的序列作为结果存储在 facts 变量中。 - rhu
这确保了您永远不会遇到StackOverflowErrors?真的吗? - raven

17

Clojure 有多种方法可以避免递归

  • 使用recur 进行显式的尾调用。(必须是真正的尾调用,否则将无法工作)
  • 惰性序列正如上面提到的。
  • trampolining,您返回一个执行工作的函数而不是直接执行该函数,然后调用一个 trampoline 函数,该函数重复调用其结果,直到其变为实际值而不是函数。
  • (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函数?


  • 1
    该函数在REPL中返回错误,问题在于一个函数返回的值不能被前一个函数乘以。 ClassCastException utilities$fact$fn__16548 无法转换为 java.lang.Number clojure.lang.Numbers.multiply (Numbers.java:146)。我的函数将与@Anon的函数相似 (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

    3

    我准备发布以下内容时,发现与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.


    2
    我还不能将它完全翻译成Clojure,所以我很感激你能够做到,即使没有人喜欢我的观点,即延续传递风格是真正的解决方案 :) - JasonTrue
    谢谢。我不是Scheme程序员,所以我只能就这个Clojure代码发表意见,它看起来基本上就是你的示例所做的事情。在这里,我没有传递一个continuation函数,而只是(在内部的“worker”函数中)传递了额外的累加器值,该值在每次调用时都会更新。从我所读到的内容来看,我对CPS的理解是,所有函数都需要一个额外的continuation函数来指定下一步要调用什么,而CPS需要尾调用优化来避免堆栈增长,而不是作为缺乏尾调用优化的解决方法。 - Anon

    1

    堆栈深度是一个小烦恼(但可配置),但即使在具有尾递归的语言(如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))))))
    

    1

    正如l0st3d所建议的那样,考虑使用recurlazy-seq

    此外,尝试通过使用内置序列形式来构建序列,而不是直接构建序列,使其成为惰性序列。

    以下是使用内置序列形式创建惰性斐波那契序列的示例(来自《Programming Clojure》书):

    (defn fibo []
      (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
    
    => (take 5 (fibo))
    (0 1 1 2 3)
    

    0
    补充Siddhartha Reddy的答案,您也可以从计算机程序的构造和解释中借鉴阶乘函数,并进行一些特定于Clojure的调整。即使是非常大的阶乘计算,我也得到了相当不错的性能。
    (defn fac [n]
      ((fn [product counter max-count]
         (if (> counter max-count)
             product
             (recur (apply *' [counter product])
                    (inc counter)
                    max-count)))
       1 1 n))
    

    0

    另一个简单的递归实现可能是这样的:

    (defn fac [x]
        "Returns the factorial of x"
        (if-not (zero? x) (* x (fac (- x 1))) 1))
    

    -8

    阶乘数由于其本质的巨大性质而变得非常大。我不确定Clojure如何处理这个问题(但我确实看到它与java一起工作),但是任何不使用大数的实现都会非常快地溢出。

    编辑:这还没有考虑到您正在使用递归,这也很可能会耗尽资源。

    编辑x2:如果实现使用大数,通常是数组,再加上递归(每个函数入口一个大数副本,由于函数调用始终保存在堆栈上),这将解释为什么会发生堆栈溢出。尝试在for循环中执行以查看是否存在该问题。


    2
    然后我期望看到的是类似于“整数溢出”,而不是“堆栈溢出”。 - GabiMe
    之所以出现 StackOverflow,是因为你的代码本质上在方法调用中不断地嵌套方法调用,直到超出栈帧的范围。 - cdmckay
    此外,值得一提的是,Clojure拥有任意精度数值类型。这意味着您永远不会在纯Clojure代码中遇到整数溢出问题。 - cdmckay
    没有理由将“大整数”存储在堆栈上。也许它们的引用存储在堆栈上,但我怀疑整个值是否存储在堆栈上。 - pauldoo
    +1 踩,她是对的。@cdmckay ;; Clojure 1.5.0-beta2 => (fact 400) ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388) - m0skit0
    2
    如果我们使用 *' 而不是 *,它不会在溢出时抛出异常,而是动态地使用所需的类型。 - m0skit0

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接