CODEWITHSUNDEEP
clojuretail-recursion
Kevin
Kevin

Reputation: 25259

convert recursive function to use tail recursion

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?

Upvotes: 4

Views: 214

Answers (4)

Jean-Louis Giordano
Jean-Louis Giordano

Reputation: 1967

You can solve this elegantly without using recursion:

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

Upvotes: 3

mobyte
mobyte

Reputation: 3752

1st variant

(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)))))

Upvotes: 2

number23_cn
number23_cn

Reputation: 4619

add lazy-seq:

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

Upvotes: 1

kotarak
kotarak

Reputation: 17299

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

Upvotes: 3

Related Questions