Is recursion an odor (in idiomatic Clojure) due to lightning and HOF?

Question

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

• You can solve most problems in a recursive way (instead of using loops) (assuming you have tail call optimization)
• Lisp is great because it is easy to implement on its own.

Now you might think that this is true for all Lispy languages ​​(including Clojure). The trouble is that the book is an artifact of its time (1989), probably before Functional Programming with Higher Order Functions (HOFs) - this is what we have today (or, at least, was considered acceptable for students).

The advantage of recursion (at least in part) is that it is easy to traverse nested data structures such as ('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 go through them, like 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 looks like you can solve any problem with a workaround in the list:

• a zipper as described above, or
• a zipper that looks at the structure and returns a set of keys that will allow you to change the structure using assoc .

Assumptions:

• I assume, of course, data structures that are fixed in size and fully known before crawling
• I exclude the streaming data source script.

My question is: Odor recursion (in idiomatic Clojure) due to lightning and HOF?

Answer 1

I would say yes, if you do manual recursion, you should at least reconsider whether you need to do this. But I would not say that lightning has anything to do with it. My experience with zippers was that they are theoretically used and very interesting for Clojure newbies, but have little practical value when you get everywhere because situations in which they are useful rarely disappear.

This is really because of higher order functions that have already implemented common recursive patterns for you, that manual recursion is unusual. However, of course, it is not necessary that you never use manual recursion: it is just a warning sign, suggesting that you can do something else. I can’t even remember the situation in four years of using Clojure, that I actually need lightning, but I often use recursion.

Answer 2

Clojure Idioms prevent explicit recursion because the call stack is limited: usually to a depth of about 10 thousand. Amendment of the first of the Halloway and Bedra Six Clojure Functional Programming Rules ( Clojure Programming (p. 89)),

Avoid unlimited recursion. The JVM cannot optimize recursive calls and Clojure programs that recurs without restrictions will beat 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
  through an expanding data structure. Many HOFs in a library sequence, such as map and filter , do this.