Transforming an accumulating mundane recursive fn into a tail-recursive fn (with Clojure)

Mar 8, 2011

this example is in Clojure, but the general principle stands regardless of language

Transforming an accumulating mundane recursive function to a tail-recursive function using a helper function.

(defn mundane-pack
"Mundane recursive way to pack a sequence"
[[f & r :as S]]
(if (seq S)
(let [[packed tail] (split-with {f true} S)]
(if (seq tail)
(cons packed (mundane-pack tail))
[packed]))
[nil]))

(defn pack
"Tail-recursive way to pack a sequence"
[coll]
(letfn [(pack* [[f & r :as S] acc]
(when (seq S)
(let [[packed tail] (split-with {f true} S)]
(if (seq tail)
(recur tail (conj acc packed))
(conj acc packed)))))]
(pack* coll [])))

(defn rle
"Run-length encode a sequence"
[coll]
(map #(vector (count %) (first %))
(pack coll)))

(def S '[a a a a b c c a a d e e e e])

(pack S)
;=> [(a a a a) (b) (c c) (a a) (d) (e e e e)]

(rle S)
;=> ([4 a] [1 b] [2 c] [2 a] [1 d] [4 e])

:f

1. You should also mention the third option to rewrite list-accumulating mundane recursive fns in Clojure: laziness. lazy-pack is (partial partition-by identity) but implemented this way it obviously misses the point of the exercise.

2. @cgrand

Indeed. I had another post in me that would cover that very ground, but maybe your comment will suffice. :-)

3. Forgive me if I’m misunderstanding things, but should the symbol pack be mundane-pack in the first function?

4. @Sam

You are absolutely correct. Thanks.

5. Paul

A good technique to know. I would have used loop instead of leftn. For some reason I never seem to use the latter.