Что я делаю неправильно? Простая рекурсия в несколько тысяч вызовов глубиной бросает 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)
Размер стека, я понимаю, зависит от используемой вами 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.
Изменить: для записи здесь используется функция 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)
Здесь другой способ:
(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 вручную, но не так много в моем опыте.
Clojure имеет несколько способов рекурсии busting
явные хвостовые вызовы с recur. (они должны быть истинно хвостами, так что это не будет работать) Ленивые последовательности, как указано выше. trampolining, где вы возвращаете функцию, которая выполняет эту работу, вместо того, чтобы делать это напрямую, а затем вызывает функцию батута, которая повторно называет ее результат до тех пор, пока она не превратится в реальное значение вместо функции.
(defn fact ([x] (trampoline (fact (dec x) x)))
([x a] (if (<= x 1) a #(fact (dec x) (*' x a)))))
(fact 42)
620448401733239439360000N
memoizing тот факт, что это действительно может сократить глубину стека, хотя это обычно не применимо.
ps: У меня нет ответа на меня, так что бы кто-то любезно протестировал функцию фиксации ловушки?
Поскольку я собирался опубликовать следующее, я вижу, что он почти такой же, как пример схемы, отправленный 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
и др.
Как предложено 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)
Глубина стека - небольшая досада (но настраиваемая), но даже на языке с хвостовой рекурсией, такой как Scheme или F #, у вас в конечном итоге закончится пространство стека с вашим кодом.
Насколько я могу судить, ваш код вряд ли будет оптимизирован для хвостовой рекурсии даже в среде, которая прозрачно поддерживает рекурсию хвоста. Вы хотите посмотреть стиль продолжения, чтобы минимизировать глубину стека.
Вот канонический пример в Схеме из Wikipedia, который можно было бы перевести на Clojure, F # или другой функциональный язык без особого Проблема:
(define factorial
(lambda (n)
(let fact ([i n] [acc 1])
(if (zero? i)
acc
(fact (- i 1) (* acc i))))))
Другой простой простой рекурсивной реализацией может быть следующее:
(defn fac [x]
"Returns the factorial of x"
(if-not (zero? x) (* x (fac (- x 1))) 1))
Чтобы добавить к ответу Сиддхартхи Редди, вы также можете взять факториальную функцию Структура и интерпретация компьютерных программ, с некоторыми 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))
Факториалы по своей природе очень большие. Я не уверен, как это работает с Clojure (но я вижу, что он работает с java), но любая реализация, которая не использует большие числа, будет очень быстро переполняться.
Изменить: это не принимая во внимание тот факт, что для этого вы используете рекурсию, которая также может использовать ресурсы.
Изменить x2: если реализация использует большие числа, которые, насколько мне известно, обычно являются массивами, в сочетании с рекурсией (одна копия большого числа на запись функции, всегда сохраняемая в стеке из-за вызовов функций) объясните переполнение стека. Попробуйте сделать это в цикле for, чтобы убедиться, что это проблема.