recursion - Clojure 尾递归与素数

Question

我正在尝试自学 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))

我最终遇到堆栈溢出错误。我知道我需要把它变成一个适当的 recur 循环，但我看到的所有例子似乎都太简单了，只指向一个计数器或数值变量作为焦点。我如何使这个递归？

谢谢!

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递归结束时的调用是可选的，只要您不关心因子是否以它们被发现的相反顺序列出。