Recursion and recur

Recursion is the functional alternative to for/while loops: a function calls itself with a smaller version of the problem until a base case is hit. Clojure runs on the JVM, which does not automatically eliminate tail calls, so a naive deep recursion will blow the stack. The recur form solves this: it tells the compiler "this self-call is in tail position, please loop instead of growing the stack."

Minimal example

A naive recursive sum — clear, but stack-bound. It works for small inputs:

recur turns the same idea into a constant-stack loop. The recursive call must be in tail position (nothing left to do after it). The compiler verifies that for you:

The accumulator pattern is the trick: instead of waiting on the result of the recursive call (which would need the stack), you carry the in-progress answer forward as an argument.

Self-recursive functions

recur works inside loop (as above) but also inside defn directly, re-invoking the function with new arguments:

Read carefully: the example above is wrong — recur can only pass the new argument list, but (* n (dec n)) is not a value for the parameter n, it's part of the result. A correct accumulator version:

Mutual recursion

Two functions calling each other can't recur across the call boundary. Use trampoline instead: each function returns a thunk (a function of no args), and trampoline keeps invoking returned thunks until it gets a plain value.

Check yourself

Exercise

Implement my-count using loop/recur so it runs in constant stack space even on a 1,000,000-element collection.