Recursion

Run each complete example in the Playground. Each example shows its result below the code.

Add four numbers

(let loop ((xs (list 1 2 3 4)) (sum 0))
  (if (null? xs)
      sum
      (loop (cdr xs) (+ sum (car xs)))))

10

The name loop after let lets the body call itself. This is a named let. A procedure calling itself is recursion.

Here, xs holds the items still to add. The parameter sum holds the total so far. A parameter that carries a partial result between calls is an accumulator.

null? returns true for an empty list. When xs is empty, the procedure returns sum without another call. This stopping case is the base case.

Each recursive call passes (cdr xs), the list without its first item. A finite proper list therefore reaches the base case. An empty input list returns the initial total, 0.

Find the tail call

The arguments (cdr xs) and (+ sum (car xs)) are computed before the next call to loop. Its result becomes the current call's result directly. There is no addition left to perform after it returns.

A call in this position is a tail call. Lispex reuses the current call's continuation, the work that remains after the call returns. Repeated tail calls therefore keep the depth of pending calls constant.

The loop still performs work for each item. Its running time and data memory use still depend on the program and input, and resource limits still apply.

Write the same loop with do

(do ((rest (list 1 2 3 4) (cdr rest))
     (sum 0 (+ sum (car rest))))
    ((null? rest) sum))

10

Each variable has an initial value and a next value. At each step, do computes both next values using the current rest and sum. When rest is empty, it returns sum.

Lispex translates do into a recursive loop with a tail call. Omitting the result after the stopping test makes do return zero values. See conditionals and derived forms for the full syntax.

Try another input

Add 5 to the first example's input list. What result should it produce? Does the recursive call remain a tail call?

To replace work after a recursive call with an accumulator, read proper tail calls. That page also covers two procedures calling each other, called mutual recursion.

For a list operation that already has a suitable procedure, use the higher-order procedure reference.