В clojure я хотел бы написать функцию хвостовой рекурсии, которая запоминает результаты промежуточного для последующих вызовов.
[EDIT: этот вопрос был переписан с использованием gcd
в качестве примера вместо factorial
.]
Мемуаризованный gcd
(наибольший общий делитель) может быть реализован следующим образом:
(def gcd (memoize (fn [a b]
(if (zero? b)
a
(recur b (mod a b))))
В этой реализации результаты промежуточного не сохраняются в памяти для последующих вызовов. Например, чтобы вычислить gcd(9,6)
, gcd(6,3)
вызывается как промежуточный результат. Тем не менее, gcd(6,3)
не сохраняется в кеше memoized функции, потому что точка рекурсии recur
является анонимной функцией, которая не memoized.
Следовательно, если после вызова gcd(9,6)
, мы вызываем gcd(6,3)
, мы не будем использовать мемуаз.
Единственное решение, о котором я могу думать, это использовать обычную рекурсию (явно gcd
вместо recur
), но тогда мы не будем использовать оптимизацию Tail Call Optimization.
Нижняя линия
Есть ли способ достичь обоих:
- Оптимизация звонков
- Запоминание промежуточных результатов для последующих вызовов
Примечания
- Этот вопрос похож на Объединить memoization и tail-recursion. Но все ответы там связаны с
F#
. Здесь я ищу ответ вclojure
. - Этот вопрос оставлен как упражнение для читателя Радость Clojure (глава 12.4). Вы можете ознакомиться с соответствующей страницей книги в http://bit.ly/HkQrio.