Рекурсия хвоста в clojure

Это код lisp, который использует рекурсию хвоста.Рекурсия хвоста в clojure

(defun factorial (f n) 
    (if (= n 1) 
     f 
     (factorial (* f n) (- n 1))))

Я переводил это в код clojure, ожидая такой же оптимизации хвостовой рекурсии.

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

Однако я получил это целочисленное переполнение (не переполнение стека) даже с небольшим числом, таких как (fact 1 30).

ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1374)

Я пробовал с recur, но получил ту же ошибку.

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

Что не так с кодом clojure?

источник

2013-05-20 prosseek

Также стоит отметить, что Clojure, из-за ограничений JVM, не поддерживает автоматическую оптимизацию хвостового вызова. 'recur' - это действительно способ найти рекурсивную идиому в этом случае. – JohnJ

Где в документах clojure я могу найти примеры использования recur без цикла? То, как вы использовали его здесь. – SultanLegend

Ничего, просто использовать BigInt S:

(factorial 1N 30N) ;=> 265252859812191058636308480000000N

Аргументы могут быть небольшими, но результат не так!

Обратите внимание, что тикали версии арифметических операторов, также доступны, которые поддерживают произвольную точность:

(reduce *' (range 1 31)) ;=> 265252859812191058636308480000000N

источник

2013-05-20 18:10:16

ответ

Смежные вопросы