преобразовать рекурсивную функцию для использования хвостовой рекурсии

Скажем, у меня есть такая функция:

user=> (def m {10 5, 5 2, 2 1})
#'user/m
user=> (defn hierarchy [x] (when x (cons x (hierarchy (get m x)))))
#'user/hierarchy
user=> (hierarchy 10)
(10 5 2 1)
user=>

И, очевидно, здесь это нормально, потому что глубина стека будет небольшой. Но для этого общего типа проблемы, когда я создаю список, который хочу вернуть, рекурсивный вызов всегда заканчивается вызовом cons. Как мне преобразовать это в хвостовую рекурсию, чтобы я мог использовать повторение и не занимать место в стеке?


clojure tail-recursion
person Kevin    schedule 06.11.2012    source источник

Ответы (4)


arrow_upward
2
arrow_downward

1 вариант

(defn hierarchy* [res x]
  (if-not x
    res
    (recur (conj res x) (get m x))))

(defn hierarchy [x]
  (hierarchy* [] x))

2nd

(defn hierarchy [x]
  (loop [res []
         next-x x]
    (if-not next-x
      res
      (recur (conj res next-x) (get m next-x)))))
person mobyte    schedule 06.11.2012
comment
Для 1-й реализации вам не нужно определять отдельную функцию hierarchy*. В Clojure можно определить разное поведение для разного количества аргументов clojure.org/functional_programming. - person Alexey Kachayev; 06.11.2012
comment
отметив это как правильное. Я ценю все ответы, но это ближе всего к тому, что я пытался понять (даже если есть другие, возможно, лучшие способы сделать это в clojure). - person Kevin; 06.11.2012

arrow_upward
3
arrow_downward

Прочтите об аккумуляторах.

В Clojure эту конкретную проблему можно решить с помощью lazy-seq. lazy-seq откладывает вычисление, поэтому переполнение стека (обычно) не является проблемой.

(defn hierarchy
  [x]
  (when x
    (lazy-seq
      (cons x (hierarchy (get m x))))))
person kotarak    schedule 06.11.2012
comment
Возможно, вы могли бы добавить, что lazy-seq откладывает вычисление рекурсивного вызова до тех пор, пока вызывающий экземпляр функции не завершится, поэтому рекурсивные вызовы фактически никогда не находятся в одном и том же стеке. Удерживание головы может по-прежнему истощать память, но не из-за переполнения стека. - person Rafał Dowgird; 06.11.2012
comment
Вы все еще можете столкнуться с переполнением стека, когда вы накладываете последовательность на последовательность на последовательность. Пример: (loop [x (seq some-input) s nil]) (if s (recur (next x) (concat (do-stuff (first x)) s)) s)). При реализации возвращенного s вы запускаете ряд реализаций каскада concat, который может привести к переполнению стека. - person kotarak; 06.11.2012

arrow_upward
3
arrow_downward

Вы можете решить эту проблему элегантно, не используя рекурсию:

(defn hierarchy [x]
  (take-while identity (iterate m x)))
person Jean-Louis Giordano    schedule 06.11.2012
comment
Вы даже можете избавиться от partial и использовать m напрямую. - person kotarak; 06.11.2012
comment
спасибо, мне было интересно, есть ли способ сделать это без явной рекурсии. - person Kevin; 06.11.2012

arrow_upward
1
arrow_downward

добавить lazy-seq:

(defn hierarchy [x] (when x (cons x (lazy-seq (hierarchy (get m x))))))
person number23_cn    schedule 06.11.2012