Recursion and Looping Constructs in Clojure

Recursion: Solving a problem by defining a function in terms of smaller instances of the same problem.

Recursion matters in Clojure because the language leans toward value transformation rather than mutable loop counters. But one important correction comes first: Clojure does not provide general automatic tail-call optimization for arbitrary recursive calls. What it gives you is the explicit recur form, which is how you write efficient self-recursive or loop-recursive iteration.

That distinction is crucial. If you think “Clojure optimizes all recursion automatically,” you will eventually write stack-blowing code and be surprised.

Ordinary Recursion First

Simple structural recursion is often the clearest tool when the problem naturally breaks itself down.

1(defn sum-list [xs]
2  (if (empty? xs)
3    0
4    (+ (first xs)
5       (sum-list (rest xs)))))

This is easy to read:

• the empty list returns 0
• otherwise add the first element to the recursive sum of the rest

For small or naturally recursive problems, this style is fine. The danger appears when recursion depth grows and there is no recur in tail position to reuse the stack frame.

What recur Actually Does

recur does not mean “call this function again somehow.” It means “jump back to the nearest recursion point with new values, provided the call is in tail position.”

That recursion point can be:

• the current function
• a loop

If recur is not in tail position, Clojure rejects it.

loop and recur

loop creates a local recursion point with named bindings. recur jumps back to it efficiently.

1(loop [i 0
2       acc []]
3  (if (= i 5)
4    acc
5    (recur (inc i) (conj acc i))))
6;; => [0 1 2 3 4]

This is Clojure’s direct answer to many imperative loops:

• bindings hold the current state
• recur advances the state
• the final branch returns the result

No mutable loop variable is required.

Tail Position Is the Real Rule

A call is in tail position when its result is returned directly without additional work afterward.

This is valid:

1(defn countdown [n]
2  (if (zero? n)
3    :done
4    (recur (dec n))))

This is not tail-recursive:

1(defn bad-sum [n]
2  (if (zero? n)
3    0
4    (+ n (bad-sum (dec n)))))

Why not? Because after the recursive call returns, the function still has to add n. The recursive call is not the final action.

That is why a naïve recursive factorial or sum may still overflow the stack on large input.

Converting to Tail Recursion

When you want recursion to scale, introduce an accumulator and move the recursive step into recur.

1(defn sum-to [n]
2  (loop [i n
3         acc 0]
4    (if (zero? i)
5      acc
6      (recur (dec i) (+ acc i)))))

Now the state needed for the next step is explicit:

• current counter i
• accumulated result acc

The recursive step is in tail position, so recur can reuse the frame.

Recursion Versus Sequence Operations

Do not reach for explicit recursion too quickly. Many Clojure problems are better expressed with existing sequence and collection operations:

1(reduce + [1 2 3 4 5])
2;; => 15
3
4(map inc [1 2 3])
5;; => (2 3 4)

Strong Clojure style usually prefers:

• map, filter, reduce, into, and friends for collection transformations
• loop/recur when you genuinely need step-by-step control
• direct structural recursion when the problem itself is recursive

That order matters. Not every loop-shaped problem needs explicit loop.

A Good Use for loop

loop is especially good when:

• you are carrying several pieces of evolving state
• you need explicit termination logic
• the problem is iterative but not well-expressed by one higher-order collection function

1(defn find-first-duplicate [xs]
2  (loop [remaining xs
3         seen #{}]
4    (when-let [x (first remaining)]
5      (if (contains? seen x)
6        x
7        (recur (rest remaining) (conj seen x))))))

That is a good loop because the state transition is explicit and meaningful.

Trampoline and Mutual Recursion

When recursion cannot be expressed with a simple tail-recursive recur, trampoline can sometimes help.

 1(defn even-step [n]
 2  (if (zero? n)
 3    true
 4    #(odd-step (dec n))))
 5
 6(defn odd-step [n]
 7  (if (zero? n)
 8    false
 9    #(even-step (dec n))))
10
11(trampoline even-step 100000)
12;; => true

This is not the first tool to reach for in everyday code, but it is useful to know when mutually recursive processes would otherwise keep growing the stack.

Common Mistakes

Assuming Clojure Has General Tail-Call Optimization

It does not. recur is explicit, restricted, and intentional.

Writing Recursive Code When reduce Would Be Clearer

If you are just folding a collection to one answer, start with reduce before writing custom recursion.

Hiding State Transitions

If a loop has five bindings with cryptic names, the recursion may be technically correct but still hard to understand. The evolving state should tell a readable story.

Forgetting That rest and next Behave Differently

When writing list or seq recursion, small details about empty tails matter. These are exactly the places where built-in sequence functions often save you from subtle edge handling.

Design Review Question

A developer writes a recursive list-processing function that works fine for small inputs but overflows the stack on large ones. They assume the JVM is the problem because “functional languages optimize recursion anyway.”

What is the stronger explanation?

The stronger explanation is that the code is probably not tail-recursive in a way Clojure can optimize with recur. The fix is not to blame the JVM abstractly. The fix is to redesign the function using loop/recur, an accumulator, reduce, or another iteration strategy that matches the problem shape.

Key Takeaways

• ordinary recursion is clear for naturally recursive problems
• Clojure does not automatically optimize all recursive calls
• recur is the explicit tool for efficient tail recursion
• loop and recur are often the right replacement for imperative looping
• many collection problems are still clearer with map, filter, or reduce