Przepełnienie podczas używania recur w clojure

Question

Mam prosty kalkulator liczby pierwszej w clojure (nieefektywny algorytm, ale próbuję po prostu zrozumieć zachowanie powtarzam na teraz). Kod to:

(defn divisible [x,y] (= 0 (mod x y))) 

(defn naive-primes [primes candidates] 
    (if (seq candidates) 
     (recur (conj primes (first candidates)) 
       (remove (fn [x] (divisible x (first candidates))) candidates)) 
     primes) 
) 

Działa tak długo, jak długo nie próbuję znaleźć zbyt wielu liczb. Na przykład:

(print (sort (naive-primes [] (range 2 2000)))) 

działa. W przypadku wszystkiego, co wymaga większej rekurencji, pojawia się błąd przepełnienia.

(print (sort (naive-primes [] (range 2 20000)))) 

nie będzie działać. Zasadniczo, czy używam recur lub call naive-primes ponownie bez próby TCO, nie wydaje się, aby robiło to jakąś różnicę. Dlaczego otrzymuję błędy w przypadku dużych rekursji podczas korzystania z funkcji recur?

Answer 1

recur zawsze używa rekursji ogonowej, niezależnie od tego, czy powracasz do pętli, czy też do funkcji. Problem dotyczy połączeń z numerem remove. remove dzwoni pod numer , aby uzyskać element z odpowiedniego seq i sprawdza, czy dany element jest prawidłowy. Jeśli bazowe polecenie seq zostało utworzone przez połączenie z numerem remove, otrzymasz kolejne połączenie z numerem first. Jeśli wywołasz remove 20000 razy na tym samym seq, wywołanie first wymaga wywołania first 20000 razy, a żadne z połączeń nie może być rekursywne. W związku z tym błąd przepełnienia stosu.

Zmiana (remove ...) do (doall (remove ...)) rozwiązuje problem, ponieważ zapobiega nieskończoną układanie remove połączeń (każdy dostaje w pełni zastosowane natychmiast i zwraca konkretny nast nie leniwy nast). Myślę, że ta metoda ma tylko jedną listę zapisów w pamięci w jednym czasie, choć nie jestem tego pewien. Jeśli tak, to nie jest to zbyt mało wydajne miejsce, a niektóre testy pokazują, że nie jest to dużo wolniejsze.