По какой-то причине мне трудно придумать хороший способ переписать эту функцию, чтобы она использовала постоянное пространство стека. В большинстве онлайн-дискуссий о мошенничестве с рекурсией дерева используется функция Фибоначчи и свойства этой конкретной проблемы. Есть ли у кого-нибудь идеи для этого «реального мира» (ну, более реального мира, чем ряд Фибоначчи) использования рекурсии?
Clojure представляет собой интересный случай, поскольку в нем нет оптимизации хвостового вызова, а только хвостовая рекурсия через специальную форму "recur". Это также настоятельно не рекомендует использовать изменяемое состояние. В нем много ленивых конструкций, включая tree-seq, но я не вижу, как они могут мне помочь. для этого случая. Может ли кто-нибудь поделиться некоторыми методами, которые они почерпнули из C, Scheme, Haskell или других языков программирования?
(defn flatten [x]
(let [type (:type x)]
(cond (or (= type :NIL) (= type :TEXT))
x
(= type :CONCAT)
(doc-concat (flatten (:doc1 x))
(flatten (:doc2 x)))
(= type :NEST)
(doc-nest (:level x)
(flatten (:doc x)))
(= type :LINE)
(doc-text " ")
(= type :UNION)
(recur (:doc1 x)))))
редактировать: По запросу в комментариях...
В общих чертах и с использованием схемы - как мне переписать следующий шаблон рекурсии, чтобы он не занимал пространство стека или не требовал оптимизации хвостового вызова для несамостоятельных вызовов?
(define (frob x)
(cond ((foo? x)
x)
((bar? x)
(macerate (f x) (frob (g x))))
((thud? x)
(frobnicate (frob (g x))
(frob (h x))))))
Я выбрал раздражающие имена, чтобы показать, что я ищу ответы, которые не полагаются на алгебраические свойства x, macerate, frobnicate, f, g или h. Я просто хочу переписать рекурсию.
ОБНОВЛЕНИЕ:
Рич Хики любезно добавил в Clojure явную функцию батута.