Is recursion a smell (in idiomatic Clojure) because of of zippers and HOFs?

Question

The classic book The Little Lisper (The Little Schemer) is founded on two big ideas

1. You can solve most problems in a recursive way (instead of using loops) (assuming you have Tail Call Optimisation)
2. Lisp is great because it is easy to implement in itself.

Now one might think this holds true for all Lispy languages (including Clojure). The trouble is, the book is an artefact of its time (1989), probably before Functional Programming with Higher Order Functions (HOFs) was what we have today.(Or was at least considered palatable for undergraduates).

The benefit of recursion (at least in part) is the ease of traversal of nested data structures like ('a 'b ('c ('d 'e))).

For example:

(def leftmost
  (fn [l]
    (println "(leftmost " l)
    (println (non-atom? l))
    (cond
      (null? l) '()
      (non-atom? (first l)) (leftmost (first l))
      true (first l))))

Now with Functional Zippers - we have a non-recursive approach to traversing nested data structures, and can traverse them as we would any lazy data structure. For example:

(defn map-zipper [m]
  (zip/zipper 
    (fn [x] (or (map? x) (map? (nth x 1))))
    (fn [x] (seq (if (map? x) x (nth x 1))))
    (fn [x children] 
      (if (map? x) 
        (into {} children) 
        (assoc x 1 (into {} children))))
    m))

(def m {:a 3 :b {:x true :y false} :c 4})

(-> (map-zipper m) zip/down zip/right zip/node)
;;=> [:b {:y false, :x true}]

Now it seems you can solve any nested list traversal problem with either:

• a zipper as above, or
• a zipper that walks the structure and returns a set of keys that will let you modify the structure using assoc.

Assumptions:

• I'm assuming of course data structures that fixed-size, and fully known prior to traversal
• I'm excluding the streaming data source scenario.

My question is: Is recursion a smell (in idiomatic Clojure) because of of zippers and HOFs?

Answer 1

I would say that, yes, if you are doing manual recursion you should at least reconsider whether you need to. But I wouldn't say that zippers have anything to do with this. My experience with zippers has been that they are of theoretical use, and are very exciting to Clojure newcomers, but of little practical value once you get the hang of things, because the situations in which they are useful are vanishingly rare.

It's really because of higher-order functions that have already implemented the common recursive patterns for you that manual recursion is uncommon. However, it's certainly not the case that you should never use manual recursion: it's just a warning sign, suggesting you might be able to do something else. I can't even recall a situation in my four years of using Clojure that I've actually needed a zipper, but I end up using recursion fairly often.

Answer 2

Clojure idioms discourage explicit recursion because the call stack is limited: usually to about 10K deep. Amending the first of Halloway & Bedra's Six Rules of Clojure Functional Programming (Programming Clojure (p 89)),

Avoid unbounded recursion. The JVM cannot optimize recursive calls and Clojure programs that recurse without bound will blow their stack.

There are a couple of palliatives:

• recur deals with tail recursion.
• Lazy sequences can turn a deep call stack into a shallow call stack
  across an unfolding data structure. Many HOFs in the sequence
  library, such as map and filter, do this.