Recursion and recur

Recursion is the functional alternative to f‌o‌rclojure.core/forList comprehension; lazy. (for [x xs :when (p x)] (f x)).view on clojuredocs →/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 r‌e‌c‌u‌rclojure.core/recurTail-recursive call to the enclosing loop or fn.view on clojuredocs → 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:

r‌e‌c‌u‌rclojure.core/recurTail-recursive call to the enclosing loop or fn.view on clojuredocs → 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

r‌e‌c‌u‌rclojure.core/recurTail-recursive call to the enclosing loop or fn.view on clojuredocs → works inside l‌o‌o‌pclojure.core/looplet plus a recursion target for recur.view on clojuredocs → (as above) but also inside d‌e‌f‌nclojure.core/defnDefine a named function.view on clojuredocs → directly, re-invoking the function with new arguments:

(defn factorial [n]
  (if (<= n 1)
    1
    (recur (* n (dec n))))) ;; intentional bug
 
(factorial 5)
;; → either an arity error on the JVM, or an infinite loop in ClojureScript,
;;   because `(* n (dec n))` is not "the new n" — it's part of the *result*
;;   you wanted to keep building. `recur` rebinds the arg list; here it
;;   rebinds `n` to ever-larger numbers and never reaches the base case.

A correct accumulator version:

Mutual recursion

Two functions calling each other can't r‌e‌c‌u‌rclojure.core/recurTail-recursive call to the enclosing loop or fn.view on clojuredocs → across the call boundary. Use t‌r‌a‌m‌p‌o‌l‌i‌n‌eclojure.core/trampolineBounce through fns returning fns to implement mutual recursion without growing the stack.view on clojuredocs → instead: each function returns a thunk (a function of no args), and t‌r‌a‌m‌p‌o‌l‌i‌n‌eclojure.core/trampolineBounce through fns returning fns to implement mutual recursion without growing the stack.view on clojuredocs → keeps invoking returned thunks until it gets a plain value.

Check yourself

Exercise

Implement my-count using l‌o‌o‌pclojure.core/looplet plus a recursion target for recur.view on clojuredocs →/r‌e‌c‌u‌rclojure.core/recurTail-recursive call to the enclosing loop or fn.view on clojuredocs → so it runs in constant stack space even on a 1,000,000-element collection.