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?

kotarak · Accepted Answer · 2012-11-06 06:53:13Z

3

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

answered Nov 6, 2012 at 6:53

kotarak

17.3k2 gold badges53 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rafał Dowgird Over a year ago

Perhaps you could add that lazy-seq defers the computation of the recursive call until after the calling instance of the function exits, so the recursive calls actually never live on the same stack. "Holding onto the head" might still exhaust the memory but not because of a stack overflow.

kotarak Over a year ago

You can still run into a stack overflow when you pile sequence on sequence on sequence. Example: (loop [x (seq some-input) s nil]) (if s (recur (next x) (concat (do-stuff (first x)) s)) s)). On realisation of the returned s you kick off a serious of realisations on the concat cascade, which can lead to a stack overflow.

Jean-Louis Giordano · Accepted Answer · 2012-11-06 15:41:01Z

3

You can solve this elegantly without using recursion:

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

edited Nov 6, 2012 at 15:41

answered Nov 6, 2012 at 8:25

Jean-Louis Giordano

1,96716 silver badges18 bronze badges

2 Comments

kotarak Over a year ago

You can even get rid of the partial and use m directly.

Kevin Over a year ago

thanks, I was wondering if there was a way to do it without explicit recursion.

mobyte · Accepted Answer · 2012-11-06 07:14:45Z

2

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

answered Nov 6, 2012 at 7:14

mobyte

3,7421 gold badge20 silver badges16 bronze badges

2 Comments

Oleksii Kachaiev Over a year ago

For 1st implementation you don't need to define separated function hierarchy*. In Clojure it's possible to define different behavior for different number of arguments clojure.org/functional_programming.

Kevin Over a year ago

marking this as correct. I appreciate all answers, but this comes the closest to what I was trying to understand (even if there are other, possibly better, ways of doing this in clojure).

number23_cn · Accepted Answer · 2012-11-06 06:59:25Z

1

add lazy-seq:

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

answered Nov 6, 2012 at 6:59

number23_cn

4,64929 silver badges31 bronze badges

Collectives™ on Stack Overflow

convert recursive function to use tail recursion

4 Answers 4

2 Comments

2 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related