Recursion, loop and recur

Prefer reduce, map, and other sequence functions over explicit recursion when possible.

;; Plain recursion (consumes stack)
(defn factorial [n]
  (if (<= n 1) 1 (* n (factorial (dec n)))))

;; recur: explicit tail call, constant stack (must be in tail position)
(defn factorial-tail
  ([n] (factorial-tail n 1))
  ([n acc] (if (<= n 1) acc (recur (dec n) (* acc n)))))
(factorial-tail 20)                     ; 2432902008176640000
(factorial-tail 25N)                    ; BigInt arithmetic avoids overflow

;; loop/recur: local loop
(loop [i 0 acc []]
  (if (= i 5)
    acc
    (recur (inc i) (conj acc (* i i)))))   ; [0 1 4 9 16]

;; Mutual recursion without stack growth: trampoline
(declare my-odd?)
(defn my-even? [n] (if (zero? n) true #(my-odd? (dec n))))
(defn my-odd? [n] (if (zero? n) false #(my-even? (dec n))))
(trampoline my-even? 1000000)           ; true

;; Tree walking
(require '[clojure.walk :as walk])
(walk/postwalk #(if (number? %) (inc %) %) {:a 1 :b [2 3]})   ; {:a 2, :b [3 4]}
(walk/keywordize-keys {"a" 1})          ; {:a 1}
(tree-seq coll? seq [1 [2 [3]]])        ; all nodes, depth-first