Motto: Recursive data implies recursive programs.

Our first Scheme program takes the length of a list:

  ; list-length
  ; takes a list, returns a nonnegative number
  (define (list-length lst)
   (if (null? lst)
       0
       (add1 (list-length (cdr lst)))))

Let's fill in the missing pieces. The null? primitive is a predicate that returns true (#t in Scheme) if its argument is the empty list, false (#f) otherwise. For any Scheme values X and Y, (car (cons X Y)) evaluates to X, and (cdr (cons X Y)) evaluates to Y. In Scheme, an if always has two branches. The second branch is taken if the condition evaluates to #f, otherwise the first branch is taken. You can guess what add1 does.

Note how the structure of this program follows the definition of its input data. There are two alternatives in the definition, which are reflected in the two branches for the if in the program. If you understand this, you have the central idea of the course!

Question: what does list-length do when given an atom as input?