Clojure Хвост Рекурсия с Prime Factors

Question

Я пытаюсь научить себя замыканию и для этого использую принципы Prime Factors Kata и TDD.

Через серию тестов Midje, таких как:

(fact (primefactors 1) => (list))

(fact (primefactors 2) => (list 2))

(fact (primefactors 3) => (list 3))

(fact (primefactors 4) => (list 2 2))

Мне удалось создать следующую функцию:

(defn primefactors 
    ([n] (primefactors n 2))
    ([n candidate] 
        (cond (<= n 1) (list)
              (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate)
              :else (primefactors n (inc candidate))
        )
    )
)

Это прекрасно работает, пока я не брошу на него следующий краевой тест:

(fact (primefactors 1000001) => (list 101 9901))

Я получаю ошибку переполнения стека. Я знаю, что мне нужно превратить это в правильные циклы повторения, но все примеры, которые я вижу, кажутся слишком упрощенными и указывают только на счетчик или числовую переменную в качестве фокуса. Как мне сделать это рекурсивным?

Спасибо!

Answer 1

Вот хвостовая рекурсивная реализация процедуры primefactors, она должна работать без выдачи ошибки переполнения стека:

(defn primefactors 
  ([n] 
    (primefactors n 2 '()))
  ([n candidate acc]
    (cond (<= n 1) (reverse acc)
          (zero? (rem n candidate)) (recur (/ n candidate) candidate (cons candidate acc))
          :else (recur n (inc candidate) acc))))

Хитрость заключается в использовании параметра аккумулятора для хранения результата.Обратите внимание, что вызов reverse в конце рекурсии является необязательным, если вам все равно, перечислены ли факторы в обратном порядке, в котором они были найдены.

Answer 2

Типичным способом является включение аккумулятора в качестве одного из аргументов функции. Добавьте 3-арную версию в определение вашей функции:

(defn primefactors
  ([n] (primefactors n 2 '()))
  ([n candidate acc]
    ...)

Затем измените форму (conj ...) так, чтобы она вызывала (recur ...) и передала (conj acc candidate) в качестве третьего аргумента. Убедитесь, что вы передаете три аргумента recur, т.е. (recur (/ n candidate) 2 (conj acc candidate)), так что вы вызываете 3-арочную версию primefactors.

И в случае (<= n 1) необходимо вернуть acc, а не пустой список.

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

Answer 3

Ваш второй рекурсивный вызов уже находится в хвостовых позициях, вы можете просто заменить его на recur.

(primefactors n (inc candidate))

становится

(recur n (inc candidate))

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

Первая рекурсия

(primefactors (/ n candidate))

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

Answer 4

Эта функция действительно не должна быть хвостовой рекурсивной: вместо этого она должна создавать ленивую последовательность.В конце концов, было бы неплохо знать, что 4611686018427387902 не является простым (делится на два) без необходимости разбивать числа и обнаруживать, что его другой простой множитель равен 2305843009213693951?

(defn prime-factors
  ([n] (prime-factors n 2))
  ([n candidate]
     (cond (<= n 1) ()
           (zero? (rem n candidate)) (cons candidate (lazy-seq (prime-factors (/ n candidate)
                                                                              candidate)))
           :else (recur n (inc candidate)))))

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

Answer 5

Хвостовое рекурсивное решение без ленивых последовательностей без аккумуляторов:

(defn prime-factors [n]
  (letfn [(step [n div]
            (when (< 1 n)
              (let [q (quot n div)]
                (cond
                  (< q div)           (cons n nil)
                  (zero? (rem n div)) (cons div (lazy-step q div))
                  :else               (recur n (inc div))))))
          (lazy-step [n div]
            (lazy-seq
              (step n div)))]
    (lazy-step n 2)))

Рекурсивные вызовы, встроенные в lazy-seq, не оцениваются перед итерацией по последовательности, исключая риски переполнения стека без примененияк аккумулятору.