convert recursive function to use tail recursion

Question

Say I have a function like this:

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=> 

And obviously this is fine here because the stack depth will be small. But for this general type of problem, where I'm building a list that I want to return, the recursive call always ends up inside a cons call. How would I convert this to tail recursion, so that I can use recur and not take stack space?

Answer 1

Read up on accumulators.

In Clojure this specific problem could be solved by using lazy-seq. lazy-seq defers the computation, so stack overflows are (usually) not an issue.

(defn hierarchy
  [x]
  (when x
    (lazy-seq
      (cons x (hierarchy (get m x))))))