Clojure: простой факториал вызывает переполнение стека

Question

Что я делаю не так? Простая рекурсия нескольких тысяч вызовов глубоких бросков StackOverflowError.

Если лимит рекурсий Clojure настолько низок, как я могу на него положиться?

(defn fact[x]
  (if (<= x 1) 1 (* x  (fact (- x 1))  )))

user=> (fact 2)
2

user=> (fact 4)
24

user=> (fact 4000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

Answer 1

Вот еще один способ:

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

Это не взорвет стек, потому что range возвращает ленивый seq, а reduce пересекает seq, не держась за голову.

reduce использует chunked seqs, если это возможно, так что на самом деле это может работать лучше, чем использование recur самостоятельно. Использование Siddhartha Reddy's recur версии и этой reduce версии:

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

Просто небольшая разница. Мне нравится оставлять свое кольцо recur для map и reduce и друзей, которые более читабельны и явны, и использовать recur внутри немного более элегантно, чем я могу сделать вручную. Есть моменты, когда вам нужно recur вручную, но не так много в моем опыте.

Answer 2

Размер стека, насколько я понимаю, зависит от используемой вами JVM, а также от платформы. Если вы используете Sun JVM, вы можете использовать параметры -Xss и -XThreadStackSize для установки размера стека.

Предпочтительный способ сделать рекурсию в Clojure, хотя это использовать loop / recur:

(defn fact [x]
    (loop [n x f 1]
        (if (= n 1)
            f
            (recur (dec n) (* f n)))))

Clojure выполнит для этого оптимизацию хвостового вызова; это гарантирует, что вы никогда не столкнетесь с StackOverflowError s.

И поскольку defn подразумевает привязку loop , вы можете опустить выражение loop и использовать его аргументы в качестве аргумента функции. И чтобы сделать его функцией с 1 аргументом, используйте multiary характеристику функций :

(defn fact
  ([n] (fact n 1))
  ([n f]
  (if (<= n 1)
    f
    (recur (dec n) (* f n)))))

Редактировать: Для записи вот функция Clojure, которая возвращает ленивую последовательность всех факториалов:

(defn factorials []
    (letfn [(factorial-seq [n fact]
                           (lazy-seq
                             (cons fact (factorial-seq (inc n) (* (inc n) fact)))))]
      (factorial-seq 1 1)))

(take 5 (factorials)) ; will return (1 2 6 24 120)

Answer 3

Clojure имеет несколько способов рекурсии перебора

явные хвостовые вызовы с recur . (они должны быть действительно хвостовыми вызовами, так что это не сработает) Ленивые последовательности , как указано выше. trampolining , где вы возвращаете функцию, которая выполняет работу вместо ее непосредственного выполнения, и затем вызываете функцию батута, которая несколько раз вызывает ее результат, пока не превратится в реальное значение вместо функции.

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

запоминание на самом деле это действительно может сократить глубину стека, хотя это не всегда применимо.

ps: у меня нет ответа, так что кто-то любезно протестировал бы исправление функции факта траполина?

Answer 4

Поскольку я собирался опубликовать следующее, я вижу, что это почти то же самое, что пример Scheme, опубликованный JasonTrue ... В любом случае, вот реализация в 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

и т.д.

Answer 5

Как предложил l0st3d, рассмотрите возможность использования recur или lazy-seq .

Кроме того, попытайтесь сделать вашу последовательность ленивой, построив ее, используя встроенные формы последовательности, а не делать это напрямую.

Вот пример использования встроенных форм последовательностей для создания ленивых последовательностей Фибоначчи (из книги Программирование Clojure):

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

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

Answer 6

Глубина стека является небольшим раздражением (все же настраиваемым), но даже в языке с хвостовой рекурсией, таком как Scheme или F #, вы в конечном итоге исчерпаете пространство стека с вашим кодом.

Насколько я могу судить, ваш код вряд ли будет оптимизирован для хвостовой рекурсии даже в среде, которая прозрачно поддерживает хвостовую рекурсию. Вы хотели бы взглянуть на стиль передачи продолжения, чтобы минимизировать глубину стека.

Вот канонический пример в Scheme из Wikipedia , который можно без труда перевести на Clojure, F # или другой функциональный язык:

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

Answer 7

Чтобы добавить к ответу Сиддхартхи Редди, вы также можете позаимствовать форму факторной функции Структура и интерпретация компьютерных программ с некоторыми специфическими для Clojure настройками. Это дало мне довольно хорошую производительность даже для очень больших факторных вычислений.

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

Answer 8

Другая, простая рекурсивная простая реализация может быть такой:

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

Answer 9

Факторные числа по своей природе очень велики. Я не уверен, как Clojure справляется с этим (но я вижу, что это работает с Java), но любая реализация, которая не использует большие числа, будет переполнена очень быстро.

Редактировать: Это без учета того факта, что вы используете для этого рекурсию, которая также может использовать ресурсы.

Edit x2: Если в реализации используются большие числа, которые, насколько я знаю, обычно представляют собой массивы в сочетании с рекурсией (одна копия большого числа на запись функции, всегда сохраняемая в стеке из-за вызовов функции) объяснить переполнение стека. Попробуйте сделать это в цикле for, чтобы понять, в этом ли проблема.