Tail Calls

Clojure: the JVM lacks TCO, so use recur (checked to be in tail position) and trampoline for mutual recursion. Common Lisp: SBCL performs tail-call merging under default optimization settings, but the standard doesn't guarantee it.

;; In Scheme, calls in tail position don't grow the stack (proper tail recursion)
(define (count-down n)
  (if (= n 0)
      'done
      (count-down (- n 1))))              ; tail call
(count-down 10000000)                    ; fine: constant space

;; Not a tail call: the result of the recursive call is used afterwards
(define (sum-to n) (if (= n 0) 0 (+ n (sum-to (- n 1)))))

;; Convert to a tail call with an accumulator
(define (sum-to-iter n)
  (let loop ((i n) (acc 0))
    (if (= i 0) acc (loop (- i 1) (+ acc i)))))

;; Mutual tail recursion also runs in constant space in Scheme
(define (my-even? n) (if (= n 0) #t (my-odd? (- n 1))))
(define (my-odd? n) (if (= n 0) #f (my-even? (- n 1))))
(my-even? 1000001)                       ; #f, without stack overflow

;; Continuation-passing style (CPS): every call is a tail call
(define (fact-cps n k)
  (if (= n 0)
      (k 1)
      (fact-cps (- n 1) (lambda (v) (k (* n v))))))
(fact-cps 5 (lambda (x) x))              ; 120