Recursion

Lisp's primary control flow:

(define (factorial n)
    (if (<= n 1)
        1
        (* n (factorial (- n 1)))))

(factorial 5)   ; 120

The function calls itself with a SMALLER input until base case. Standard recursion.

Mutual recursion:

(define (even? n) (if (= n 0) #t (odd? (- n 1))))
(define (odd? n) (if (= n 0) #f (even? (- n 1))))

Both functions need to find each other's binding. They must be defined in the SAME scope so recursive lookup finds them.

For tail recursion (the recursive call is the last thing the function does), some Lisps (Scheme) require TCO (tail-call optimization): reuse the current stack frame. Lets you do unbounded loops via recursion without stack overflow.

(define (loop n)
    (if (= n 0)
        "done"
        (loop (- n 1))))     ; tail call

(loop 1000000)   ; works in Scheme; blows stack in many other languages

Common Lisp doesn't require TCO; Scheme does (R5RS+).

For our toy interpreter we won't implement TCO. Calls just stack up. Add it if you want unbounded loops.