Как я могу вызвать recur в условном условии в Clojure?

Question

Я пытаюсь решить считать последовательность упражнение на 4clojure.com . Упражнение заключается в подсчете количества элементов в коллекции без использования функции count.

Я думал, что смогу сделать это через рекурсию, используя rest. Если то, что я получаю, не пусто, я возвращаю 1 + recur on the sequence rest returned. Проблема в том, что я получаю

java.security.PrivilegedActionException: java.lang.UnsupportedOperationException:
Can only recur from tail position

, хотя я и называю recur самым последним утверждением.

(fn [coll] (let [tail (rest coll)]
             (if (empty tail)
               1
               (+ 1 (recur tail)))))

Я что-то упустил?

Answer 1

Последнее утверждение - это добавление, а не вызов recur, поэтому оно не работает.Тот факт, что он внутри if, не имеет к этому никакого отношения.(fn [coll] (let [tail (rest coll)] (+ 1 (recur tail)))) тоже не сработает.

Обычный способ превратить функцию, подобную этой, в хвостовую рекурсию - заставить функцию принять второй аргумент, который содержит аккумулятор для значения, которое высложение, а затем выполнить повторение следующим образом: (recur tail (+ acc 1)) вместо попытки добавить 1 к результату recur.

Как правило: если вы что-то делаете с результатом recur (как например, добавляя к нему 1), он не может быть в хвостовой позиции, поэтому он не будет работать.

Answer 2

Ошибка, которую вы получаете, указывает на то, что ваше окончательное выражение (+ 1 (recur tail)) не оптимизируется с помощью хвостового вызова (это слово?).Проблема в том, что для оценки результата функции необходимо хранить в стеке несколько (+ 1 ...) выражений.Оптимизация хвостового вызова возможна только в том случае, если значение вызываемой функции only , необходимое для определения возврата функции, выполняющей вызов.fold.В этом случае функция должна передать остаток коллекции, а также счетчик.

(fn [count coll] (let [tail (rest coll)]
    (if (empty tail)
        count
        (recur (+ 1 count) tail)))))