Recursion basics in Lisp

Two recursions over the same list of rainfall readings, differing in where the answer accumulates.

;; the base case stops the descent; each call peels off one reading
(defun total-rainfall (readings)
  (if (null readings)
      0
      (+ (first readings) (total-rainfall (rest readings)))))

;; carrying an accumulator turns the same walk into a tail call
(defun count-dry-days (readings &optional (tally 0))
  (cond ((null readings) tally)
        ((zerop (first readings))
         (count-dry-days (rest readings) (1+ tally)))
        (t (count-dry-days (rest readings) tally))))

(defparameter *week* '(0 12 0 3 0 0 8))
(format t "~a mm fell this week~%" (total-rainfall *week*))
(format t "~a of the days were dry~%" (count-dry-days *week*))

How it works

1. total-rainfall returns 0 on (null readings) and otherwise adds (first readings) to the sum of the rest.
2. count-dry-days carries the running total in an &optional tally argument instead.
3. Its cond bumps the tally with (1+ tally) when zerop holds and passes it through unchanged otherwise.

Keywords and builtins used here

• cond
• defparameter
• defun
• first
• format
• if
• null
• rest
• zerop

The run, in numbers

Lines

16

Characters to type

606

Tokens

116

Three-star pace

75 tpm

At the three-star pace of 75 tokens a minute, this run takes about 93 seconds.

Type this snippet

Step 3 of 3 in Control flow, step 9 of 27 in Language basics.

← Previous Next →