Clojure尾数递归与素因子

我试图教自己clojure，我正在使用Prime因子卡塔和TDD的原则这样做。Clojure尾数递归与素因子

通过一系列的Midje测试是这样的：

(fact (primefactors 1) => (list)) 

(fact (primefactors 2) => (list 2)) 

(fact (primefactors 3) => (list 3)) 

(fact (primefactors 4) => (list 2 2))

我能够创建以下功能：

(defn primefactors 
    ([n] (primefactors n 2)) 
    ([n candidate] 
     (cond (<= n 1) (list) 
       (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate) 
       :else (primefactors n (inc candidate)) 
     ) 
    ) 
)

，直到我把下面的边缘情况下测试它这个伟大的工程：

(fact (primefactors 1000001) => (list 101 9901))

我结束了堆栈溢出错误。我知道我需要把它变成适当的循环，但我所看到的所有例子似乎都过于简单化，只能指出计数器或数值变量作为焦点。我如何做这个递归？

谢谢！

来源

2012-03-04 Y. Adam Martin

哇。这是我第一次看到有人正在写Lisp，他们自己写了：P – 2013-11-28 22:42:33

这里的一个尾递归实现primefactors过程，应该没有抛出一个堆栈溢出错误工作：

(defn primefactors 
    ([n] 
    (primefactors n 2 '())) 
    ([n candidate acc] 
    (cond (<= n 1) (reverse acc) 
      (zero? (rem n candidate)) (recur (/ n candidate) candidate (cons candidate acc)) 
      :else (recur n (inc candidate) acc))))

诀窍是用一个累加器参数用于存储结果。请注意，递归结束时的reverse调用是可选的，只要您不关心这些因素是否按照找到的相反顺序列出。

来源

2012-03-04 16:42:08

感谢这真棒，这是我需要的解释。 – 2012-03-04 21:33:38

在Clojure中，“recurse then reverse”是一个反模式：我们有矢量，它在右侧便宜地添加，所以最好按照正确的顺序构建列表以开始（如果需要列表而不是矢量最后，只是'seq'，它比反向便宜得多）。但是真的，懒惰的解决方案比尾递归解决方案更可取：请参阅我的答案，获取一个简单的示例。 – amalloy 2013-11-30 03:47:03

您的第二次递归调用已经在尾部位置，您可以用recur替换它。

(primefactors n (inc candidate))

成为

(recur n (inc candidate))

任何函数重载打开一个隐含的loop块，所以你不需要手工插入。这应该已经在一定程度上改善了堆栈的情况，因为这个分支将更常被采用。

第一递归

(primefactors (/ n candidate))

作为它的结果被传递到conj不在末尾位置。要将其置于尾部位置，您需要在额外的累加器参数中收集主要因素，其中您从当前递归级别获得结果，然后在每次调用时传递给recur。您需要调整终止条件以返回累加器。

来源

2012-03-04 16:09:16 pmdj

典型的方法是将累加器作为函数参数之一。添加3元数版本给你的函数定义：

(defn primefactors 
    ([n] (primefactors n 2 '())) 
    ([n candidate acc] 
    ...)

然后修改(conj ...)形式调用(recur ...)并通过(conj acc candidate)作为第三个参数。确保你通过三个参数到recur，即(recur (/ n candidate) 2 (conj acc candidate))，这样你就可以调用3-arity版本的primefactors。

而且(<= n 1)的情况下需要返回acc而不是空的列表。

如果你不能为自己找出解决方案，我可以进入更多的细节，但我想我应该给你一个机会尝试首先解决它。

来源

2012-03-04 16:09:30 liwp

A尾巴递归的，自由蓄能器，懒惰序列溶液：嵌入lazy-seq

(defn prime-factors [n] 
    (letfn [(step [n div] 
      (when (< 1 n) 
       (let [q (quot n div)] 
       (cond 
        (< q div)   (cons n nil) 
        (zero? (rem n div)) (cons div (lazy-step q div)) 
        :else    (recur n (inc div)))))) 
      (lazy-step [n div] 
      (lazy-seq 
       (step n div)))] 
    (lazy-step n 2)))

递归调用在所述序列迭代之前不被评估，从而消除了堆栈上溢的风险不诉诸到累加器。

来源

2013-11-28 20:13:04 omiel

这个函数真的不应该是尾递归的：它应该建立一个惰性序列。毕竟，知道4611686018427387902是非素数（它可以被2整除），而不必紧缩数字并发现它的其他主要因素是2305843009213693951？

(defn prime-factors 
    ([n] (prime-factors n 2)) 
    ([n candidate] 
    (cond (<= n 1)() 
      (zero? (rem n candidate)) (cons candidate (lazy-seq (prime-factors (/ n candidate) 
                       candidate))) 
      :else (recur n (inc candidate)))))

以上是您发布的算法的一个相当缺乏想象力的翻译;当然有更好的算法存在，但这会让你正确和懒惰，并修复堆栈溢出。

来源

2013-11-30 03:45:34 amalloy

Clojure尾数递归与素因子

回答

相关问题