避免抓着头

Question

欧拉项目我尝试这样的problem 3：

(defn range-start-2 [] (map #(+ % 2) (range))) 

(defn largest-prime 
    "Finds the largest prime factor of n. (n must be >= 2)" 
    [n largest-prime unchecked] 
    (cond 
    (> (first unchecked) n) 
    largest-prime 

    (= (mod n (first unchecked)) 0) 
    (recur n (first unchecked) (filter #(not= (mod % (first unchecked)) 0) unchecked)) 

    :else 
    (recur n largest-prime (filter #(not= (mod % (first unchecked)) 0) unchecked)))) 

(largest-prime (* 3 7 11 13) 2 (range-start-2)) 
;=> 13 

这适用于小的N，但给我更大的n堆栈溢出。我假设我坚持未经检查的seq的头部，但我无法弄清楚在哪里。使用它作为参数不应该保持在头上，如果它？

，我读了关闭了一只懒惰的-SEQ可能导致举行的头，让我尝试这样做：

(defn largest-prime 
    "Finds the largest prime factor of n." 
    [n largest-prime unchecked] 
    (let [prime (first unchecked)] 
    (cond 
    (> prime n) 
    largest-prime 

    (= (mod n prime) 0) 
    (recur n prime (filter #(not= (mod % prime) 0) unchecked)) 

    :else 
    (recur n largest-prime (filter #(not= (mod % prime) 0) unchecked))))) 

这也不起作用。必须有一种方法来获得懒惰seq的第一个元素的价值，而不必拘泥于它的头。

（当然也有更好的方法来解决欧拉项目的问题，但在这里我只在头保持问题感兴趣）

Answer 1

你的问题是filter呼叫“堆放”未评估。 filter不会立即应用，而是在您从序列中请求元素时应用。当你积累(filter f1 (filter f2 (filter f3 ... (filter f1000 s)...)))时，它会发出1000次调用，并最终导致堆栈溢出。

解决方案是不以这种方式使用无限延迟序列。 （如果序列是有限的，则可以避免使用doall的堆栈溢出。）

请注意，有些优化可能会使其他方法解决您的问题可行。如果你知道3,7和11是3003的因子，那么你实际上并不需要检查11和3003之间的所有可能的素数...