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

В Clojure есть несколько способов блокировки явных хвостовых вызовов рекурсии

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

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

Вот другой способ:

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

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

reduce по возможности использует сегментированные последовательности, так что это может работать лучше, чем использование recur самостоятельно. Использование версии Сиддхартхи Редди на основе рекурсии и этой версии на основе сокращения:

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 для внутреннего использования немного элегантнее, чем я делаю вручную. Бывают случаи, когда вам нужно повторять вручную,

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

и т. Д.

Глубина стека - небольшое неудобство (но настраиваемое), но даже на языке с хвостовой рекурсией, таком как 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))))))

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

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

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

Как было предложено 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)