主要因素的Clojure尾递归

Question

我正在尝试自学clojure,我正在使用Prime Factor Kata和TDD的原则来实现这一目标.

通过一系列像这样的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))

我最终得到了堆栈溢出错误.我知道我需要将其转换为适当的重复循环,但我看到的所有示例似乎都过于简单,仅指向计数器或数值变量作为焦点.如何进行递归？

谢谢!

Answer 1

这是一个尾递归实现的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递归结束时的调用是可选的,只要您不关心这些因素是否以相反的顺序列出.

Answer 2

你的第二个递归调用已经在尾部位置,你可以用它替换它recur.

(primefactors n (inc candidate))

变

(recur n (inc candidate))

任何函数重载都会打开一个隐式loop块,因此您无需手动插入.这应该已经在一定程度上改善了堆栈情况,因为这个分支将更常用.

第一次递归

(primefactors (/ n candidate))

因为结果传递给了尾部位置conj.要将它置于尾部位置,您需要在一个额外的累加器参数中收集素因子conj,然后将当前递归级别的结果传递给recur它,然后传递给每个调用.您需要调整终止条件以返回该累加器.

Answer 3

典型的方法是将累加器包含为函数参数之一.在函数定义中添加3-arity版本:

(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,而不是一个空列表.

如果你不能为自己找出解决方案,我可以详细说明,但我想我应该给你一个尝试先解决问题的机会.