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

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

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

(defn fact[x]
  (if ( (fact 2)
2

user=> (fact 4)
24

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

Ответы на вопрос(9)

я вижу, что этоЭто почти так же, как пример 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

и т.п.

 JasonTrue03 нояб. 2009 г., 20:17
Я могу'Я пока не могу перевести его на Clojure, поэтому я ценю, что вы можете, даже если никому больше не нравится моя точка зрения, что стиль передачи продолжения является реальным решением :)
 Anon04 нояб. 2009 г., 00:30
Благодарю. Я'Я не программист на Scheme, так что я могу говорить только за этот код Clojure, который, как мне показалось, по сути то, что делает ваш пример. В этом яне передавая функцию продолжения, а просто (во внутреннююработник» функция) дополнительное значение аккумулятора, которое обновляется при каждом вызове. Мое понимание стиля прохождения продолжения, как я уже прочитал, заключается в том, что все функции принимают дополнительную функцию продолжения для вызова следующего, и что CPS требует оптимизации хвостового вызова, чтобы избежать увеличения стека, а не обходного пути для отсутствие оптимизации хвостового вызова.

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

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

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

 cdmckay02 нояб. 2009 г., 18:06
Причина этого 's StackOverflow заключается в том, что ваш код по существу выполняет вызовы методов в вызовах методов, пока он не исчерпает кадры стека.
 cdmckay02 нояб. 2009 г., 18:18
Кроме того, для записи, Clojure имеет числовые типы произвольной точности. Это значит, что ты выигралникогда не получить IntegerOverflow в чистом коде Clojure.
 GabiMe02 нояб. 2009 г., 17:44
Тогда я бы ожидал увидеть что-то вродеIntegerOverflow»неПереполнение стека"
 m0skit011 мар. 2013 г., 12:04
Если мы используем*' вместо* он не вызывает переполнения, но динамически использует необходимый тип.
 pauldoo12 апр. 2011 г., 14:32
Нет причин, по которымбольшие целые числа " будет храниться в стеке. Может быть, ссылка на них хранится в стеке, но я сомневаюсь, что вся ценность.
 m0skit010 мар. 2013 г., 20:43
+1 Проголосовал и она была права. @cdmckay;; Clojure 1.5.0-beta2 => (fact 400) ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)

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

рецидивировать или желенивые-сло.

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

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

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

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

вы также можете позаимствовать форму факториальной функцииСтруктура и интерпретация компьютерных программ, с некоторыми специфичными для 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))

Вот'С другой стороны:

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

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

reduce использует chunked seqs, если это возможно, так что это может работать лучше, чем при использованииrecur сам. С помощьюСиддхартха Редди 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 вручную, но не так много в моем опыте.

 GabiMe03 нояб. 2009 г., 12:21
Классный подход .. Воспользуйтесь преимуществами ленивых последовательностей, чтобы избежать рекурсии ..
 miguelv04 дек. 2011 г., 19:47
Мне нравится это было хорошо. Кстати, также может быть:(defn factorial [n] (apply * (range 1 (inc n))))
 johnbakers09 окт. 2014 г., 20:19
@MiguelVitorino Но твоя версия сохраняет голову? Представьте, что ваш диапазон помещен в аргументы другой функции.
 Siddhartha Reddy03 нояб. 2009 г., 14:44
Я полностью согласен. Я думаю, что это лучший подход, чем прямое использование цикла / повторения, даже если разница в скорости нене существует. Я бы лично использовал только этот подход. Я дал версию loop / recur прежде всего для демонстрации рекурсии в Clojure.
 Danny Armstrong06 мая 2012 г., 02:28
В Clojure 1.3.0 я сделал эту работу для вычислений 20 письменно(defn factorial [n] (reduce *' (range 1 (inc n)))) Обратите внимание ' отметка рядом с *.

Разорение рекурсии

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

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

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

PS: У меня нет repl на меня, так что кто-то любезно протестировать-исправить функцию факта trapoline?

 Kevin Zhu10 сент. 2013 г., 08:56
Функция возвращает ошибку в REPL, проблема в том, что возвращаемая функция может 'не может быть умножено на предыдущие функции ClassCastException. $ fact $ fn__16548 нельзя преобразовать в java.lang.Number clojure.lang.Numbers.multiply (Numbers.java:146). Моя функция была бы такой же, как @Anon 'ниже(defn fact ([x] (fact x nil)) ([ x lastResult] (if (
 Arthur Ulfeldt10 сент. 2013 г., 23:20
спасибо @KevinZhu за проверку, он был полностью сломан.

но даже в языке с хвостовой рекурсией, как Scheme или F # you 'В конце концов, вам не хватит места в стеке с вашим кодом.

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

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

(define factorial
  (lambda (n)
      (let fact ([i n] [acc 1])
        (if (zero? i)
            acc
            (fact (- i 1) (* acc i))))))
Решение Вопроса

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

Предпочтительный способ сделать рекурсию в Clojure - использовать /:looprecur

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

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

И из-за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)
 raven19 мар. 2016 г., 04:29
that ensures that you’ll never run into StackOverflowErrors никогда? действительно?
 rhu31 авг. 2012 г., 22:07
@android - еще один способ сказать то же самое (начиная с Clojure 1.3):(def facts (reductions * (iterate inc 1)))
 Alexei Sholik17 мар. 2012 г., 12:27
Вот'Более элегантный способ определения бесконечной последовательности факториалов:(def facts (lazy-cat [1] (map * facts (iterate inc 2)))), затем(take 5 facts) производит.(1 2 6 24 120)

Ваш ответ на вопрос