· clojure

Clojure: A first look at recursive functions

I’m working through Stuart Halloway’s ‘Programming Clojure’ book and I just got to the section where it first mentions recursive functions.

It’s a simple function to countdown from a given number to zero and then return that sequence.

This was one of the examples from the book:

(defn countdown [result x] 
  (if (zero? x)
    (recur (conj result x) (dec x))))

That function could then be called like this:

(countdown [] 5) 

I wanted to see what the function would look if we didn’t have the empty vector as a parameter.

From playing around with F# and Scala my first thought would be to write the function like this:

(defn count-down [from]
  (defn inner-count [so-far x]
    (if (zero? x)
      (inner-count (conj so-far x) (dec x))))
  (inner-count [] from))

As the book points out a bit further on, Clojure doesn’t perform automatic tail call optimisation so we end up with a stack overflow exception if we run the function with a big enough input value.

Clojure does optimise calls to ‘recur’ so it makes more sense to use that if we want to avoid that problem.

This is an example which makes use of that:

(defn count-down [from]
  (defn inner-count [so-far x]
    (if (zero? x)
      (recur (conj so-far x) (dec x))))
  (inner-count [] from))

Looking through the Clojure mailing list at a similar problem I noticed that one of the suggestions was to arity overload the function to include an accumulator.

(defn count-down
    (count-down [] from))
  ([so-far from]
    (if (zero? from)
      (recur (conj so-far from) (dec from)))))

Written this way it feels a little bit like Haskell or Erlang but probably not idiomatic Clojure.

Anyway on the next page Halloway shows a better way to do this with much less code!

(into [] (take 5 (iterate dec 5)))

I noticed that in Scala the idea of using ‘take’ and ‘drop’ on streams of values seems to be quite popular so I’m intrigued as to whether I’ll find the same thing with Clojure.

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket