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 mx))))) #'user/hierarchy user=> (hierarchy 10) (10 5 2 1) user=> 

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

Answer 1

1st option

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

second

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

Answer 2

Read on batteries.

In Clojure, this particular problem can be solved using lazy-seq . lazy-seq rejects the calculation, so stack overflow (usually) is not a problem.

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

Answer 3

You can solve this elegantly without using recursion:

 (defn hierarchy [x] (take-while identity (iterate mx))) 

Answer 4

add lazy-seq :

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