Use Cases for Recursion in Clojure

Direct recursion is strongest when the code can mirror the shape of the data. That is the key difference from many Java loops: the recursive call is not just a repetition mechanism; it is a statement that part of the input has the same shape as the whole input.

Good Recursion Candidates

Recursive Data: Tree Size

Suppose you model a tree as maps with :children:

1(def sample-tree
2  {:id :root
3   :children [{:id :left
4               :children []}
5              {:id :right
6               :children [{:id :leaf
7                           :children []}]}]})

Counting nodes is naturally recursive because every child is another node:

1(defn tree-size [node]
2  (reduce + 1 (map tree-size (:children node))))
3
4(tree-size sample-tree)
5;; => 4

This is clearer than translating the problem into a Java-style stack by default. The recursive structure is the business rule.

Recursive Transformation: Rename Keys Deeply

Nested maps are common when Clojure code works with JSON, EDN, API payloads, or configuration. A recursive walk can express “apply this rule everywhere”:

 1(defn rename-key-deep [value from to]
 2  (cond
 3    (map? value)
 4    (into {}
 5          (map (fn [[k v]]
 6                 [(if (= k from) to k)
 7                  (rename-key-deep v from to)]))
 8          value)
 9
10    (vector? value)
11    (mapv #(rename-key-deep % from to) value)
12
13    (sequential? value)
14    (map #(rename-key-deep % from to) value)
15
16    :else
17    value))

For Java engineers, this is similar to writing a visitor, but the Clojure version is plain data in and plain data out.

Divide and Conquer: Merge Sort Shape

Divide-and-conquer algorithms often make recursion visible:

 1(defn merge-sorted [left right]
 2  (loop [xs left
 3         ys right
 4         result []]
 5    (cond
 6      (empty? xs) (into result ys)
 7      (empty? ys) (into result xs)
 8      (<= (first xs) (first ys)) (recur (rest xs) ys (conj result (first xs)))
 9      :else (recur xs (rest ys) (conj result (first ys))))))
10
11(defn merge-sort [xs]
12  (if (<= (count xs) 1)
13    xs
14    (let [v (vec xs)
15          mid (quot (count v) 2)]
16      (merge-sorted (merge-sort (subvec v 0 mid))
17                    (merge-sort (subvec v mid))))))

The outer algorithm is recursive because the same sort operation applies to smaller halves. The merge step uses loop/recur because it is a local stepping process.

Graph Traversal: Recursion With Cycle Guards

Graphs are recursive in a practical sense, but they can contain cycles. That means recursion must carry a visited set:

 1(def graph
 2  {:a [:b :c]
 3   :b [:d]
 4   :c [:d :e]
 5   :d []
 6   :e [:a]})
 7
 8(defn reachable [graph start]
 9  (letfn [(visit [seen node]
10            (if (contains? seen node)
11              seen
12              (reduce visit
13                      (conj seen node)
14                      (get graph node []))))]
15    (visit #{} start)))
16
17(reachable graph :a)
18;; => #{:a :b :c :d :e}

The important part is not just recursion. It is the invariant: never visit a node twice.

When to Avoid Direct Recursion

Practice

1. Write leaf-ids for the sample-tree map above.
2. Modify rename-key-deep so it handles sets.
3. Add cycle detection to a dependency resolver.
4. Rewrite a recursive flat-list sum into reduce and explain why it is better.

Key Takeaways

• Use recursion when the data or algorithm is structurally recursive.
• Carry invariants explicitly, especially for graphs and dependency trees.
• Combine recursion with loop/recur when only one step inside the algorithm needs a stack-safe local loop.
• Avoid direct recursion for ordinary flat collection processing.

Quiz: Recursion Use Cases