6

我正在尝试自学 clojure，并且我正在使用 Prime Factors 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))

我最终遇到堆栈溢出错误。我知道我需要将其转换为适当的递归循环，但我看到的所有示例似乎都过于简单化，只指向一个计数器或数值变量作为焦点。我如何使这个递归？

谢谢！

4

5 回答 5

12

这是该过程的尾递归实现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-04T16:42:08.843 回答
5

您的第二个递归调用已经在尾部位置，您可以将其替换为recur.

(primefactors n (inc candidate))

变成

(recur n (inc candidate))

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

第一次递归

(primefactors (/ n candidate))

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

于 2012-03-04T16:09:16.337 回答
5

典型的方法是包含一个累加器作为函数参数之一。在你的函数定义中添加一个 3-arity 版本：

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

然后修改(conj ...)表单以调用并作为第三个参数(recur ...)传递。(conj acc candidate)确保将三个参数传递给recurie (recur (/ n candidate) 2 (conj acc candidate))，以便调用primefactors.

并且(<= n 1)case需要返回acc而不是一个空列表。

如果您无法自己找出解决方案，我可以更详细地介绍，但我认为我应该给您一个机会先尝试解决。

于 2012-03-04T16:09:30.303 回答
4

这个函数真的不应该是尾递归的：它应该构建一个惰性序列。毕竟，如果知道它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-30T03:45:34.103 回答
2

尾递归、无累加器、惰性序列解决方案：

(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)))

嵌入的递归调用lazy-seq不会在迭代之前对序列进行评估，从而消除了堆栈溢出的风险，而无需求助于累加器。

于 2013-11-28T20:13:04.600 回答