Clojure: proste czynniki czynnikowe powodują przepełnienie stosu

Oto inny sposób:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

To nie rozwali stosu, ponieważ range zwraca leniwy seq i reduce przechodzi przez seq bez trzymania się głowy.

reduce korzysta z chunked seqs, jeśli może, więc może to działać lepiej niż używanie recur samodzielnie. Siddhartha Reddy ' s recur-wersja bazowa i Ta reduce-wersja bazowa:

user> (time (do (factorial-recur 20000) nil))
"Elapsed time: 2905.910426 msecs"
nil
user> (time (do (factorial-reduce 20000) nil))
"Elapsed time: 2647.277182 msecs"
nil

Clojure ma kilka sposobów przerywania rekurencji

(defn fact ([x] (trampoline (fact (dec x) x))) 
           ([x a] (if (<= x 1) a #(fact (dec x) (*' x a)))))
(fact 42)
620448401733239439360000N

Jak już miałem pisać poniżej, widzę, że jest prawie taki sam jak Przykład schematu zamieszczony przez JasonTrue... W każdym razie, oto implementacja w Clojure:

user=> (defn fact[x]
        ((fn [n so_far]
          (if (<= n 1)
              so_far
              (recur (dec n) (* so_far n)))) x 1))
#'user/fact
user=> (fact 0)
1
user=> (fact 1)
1
user=> (fact 2)
2
user=> (fact 3)
6
user=> (fact 4)
24
user=> (fact 5)
120

Itd.

Jak zasugerował l0st3d, rozważ użycie recur lub lazy-seq .

Staraj się również, aby Twoja Sekwencja była leniwa, budując ją za pomocą wbudowanych formularzy sekwencyjnych, w przeciwieństwie do robienia tego bezpośrednio.

(defn fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

=> (take 5 (fibo))
(0 1 1 2 3)

Głębokość stosu jest małą irytacją (jeszcze konfigurowalną), ale nawet w języku z rekurencją ogonową, takim jak Scheme lub F#, W końcu zabraknie miejsca na stosie z kodem.

Z tego co wiem, jest mało prawdopodobne, aby Twój kod był zoptymalizowany nawet w środowisku, które obsługuje rekurencję ogonową. Warto przyjrzeć się stylowi kontynuacji przechodzenia, aby zminimalizować głębokość stosu.

Oto kanoniczny przykład w schemacie z Wikipedii , która może być przetłumaczone na Clojure, F # lub inny język funkcjonalny bez większych problemów: {]}

(define factorial
  (lambda (n)
      (let fact ([i n] [acc 1])
        (if (zero? i)
            acc
            (fact (- i 1) (* acc i))))))

Inna, prosta rekurencyjna implementacja prosta może być następująca:

(defn fac [x]
    "Returns the factorial of x"
    (if-not (zero? x) (* x (fac (- x 1))) 1))

Aby dodać do odpowiedzi Siddharthy Reddy ' ego, możesz również pożyczyć formę funkcji czynnikowej Struktura i interpretacja programów komputerowych, z pewnymi poprawkami specyficznymi dla Clojure. To dało mi całkiem dobre wyniki nawet dla bardzo dużych obliczeń czynnikowych.

(defn fac [n]
  ((fn [product counter max-count]
     (if (> counter max-count)
         product
         (recur (apply *' [counter product])
                (inc counter)
                max-count)))
   1 1 n))

Liczby czynnikowe są z natury bardzo duże. Nie jestem pewien, jak Clojure sobie z tym radzi (ale widzę, że działa z Javą), ale każda implementacja, która nie używa dużych liczb, przepełni się bardzo szybko.

Edit: jest to bez uwzględnienia faktu, że używasz do tego rekurencji, która może również zużywać zasoby.

Edit x2: jeśli implementacja używa dużych liczb, które, o ile wiem, są zwykle tablicami, sprzężonymi z rekurencją (jeden kopiowanie dużej liczby na wpis funkcji, zawsze zapisywane na stosie ze względu na wywołania funkcji) wyjaśniałoby przepełnienie stosu. Spróbuj zrobić to w pętli for, aby zobaczyć, czy to jest problem.