Clojure尾部递归与主要因素 [英] Clojure Tail Recursion with Prime Factors

问题描述

我想教自己clojure，我使用的主要因素Kata和TDD的原则这样做。

通过一系列Midje测试this：

 （fact（primefactors 1）=>（list））
 
 （事实（原始因子3）=>（列表3））= 
 
（事实（原始因子4）=> （list 2 2））
  

我可以创建以下函数：

 （defn primefactors 
（[n]（primefactors n 2））
（[n candidate] 
 （= n 1）（列表）
（= 0（rem n候选））（conj（primefactors（/ n candidate））候选）
：else b $ b）
）
）
  

以下边缘情况测试：

 （fact（primefactors 1000001）=>（list 101 9901））
  

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

谢谢！

解决方案

一个尾递归实现 primefactors 过程，它应该工作不会引发堆栈溢出错误：

 （defn primefactors 
（[n] 
（primefactors n 2'（）））
 n1）（reverse acc）
（zero？（rem n candidate））（recur（/ n candidate）candidate（cons candidate acc））
：else ））
  

技巧是使用一个accumulator参数来存储结果。注意，在递归结束时的 reverse 调用是可选的，只要你不在意这些因素是否以相反的顺序列出。 p>

I'm trying to teach myself clojure and I'm using the principles of Prime Factors Kata and TDD to do so.

Via a series of Midje tests like this:

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

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

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

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

I was able to create the following function:

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

This works great until I throw the following edge case test at it:

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

I end up with a stack overflow error. I know I need to turn this into a proper recur loops but all the examples I see seem to be too simplistic and only point to a counter or numerical variable as the focus. How do I make this recursive?

Thanks!

解决方案

Here's a tail recursive implementation of the primefactors procedure, it should work without throwing a stack overflow error:

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

The trick is using an accumulator parameter for storing the result. Notice that the reverse call at the end of the recursion is optional, as long as you don't care if the factors get listed in the reverse order they were found.

这篇关于Clojure尾部递归与主要因素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！