Node:Every, Next:Accumulate, Previous:Recursive Patterns, Up:Recursive Patterns

Recursive Pattern: every

In the every recursive pattern, an action is performed on every element of a list.

The basic pattern is:

• If a list be empty, return nil.
• Else, act on the beginning of the list (the CAR of the list)
  • through a recursive call by the function on the rest (the CDR) of the list,
  • and, optionally, combine the acted-on element, using cons, with the results of acting on the rest.

Here is example:

(defun square-each (numbers-list)
  "Square each of a NUMBERS LIST, recursively."
  (if (not numbers-list)                ; do-again-test
      nil
    (cons
     (* (car numbers-list) (car numbers-list))
     (square-each (cdr numbers-list))))) ; next-step-expression

(square-each '(1 2 3))
    => (1 4 9)

If numbers-list is empty, do nothing. But if it has content, construct a list combining the square of the first number in the list with the result of the recursive call.

(The example follows the pattern exactly: nil is returned if the numbers' list is empty. In practice, you would write the conditional so it carries out the action when the numbers' list is not empty.)

The print-elements-recursively function (see Recursion with a List) is another example of an every pattern, except in this case, rather than bring the results together using cons, we print each element of output.

The print-elements-recursively function looks like this:

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (if list                              ; do-again-test
      (progn
        (print (car list))              ; body
        (print-elements-recursively     ; recursive call
         (cdr list)))))                 ; next-step-expression

(print-elements-recursively animals)

The pattern for print-elements-recursively is:

• If the list be empty, do nothing.
• But if the list has at least one element,
  • act on the beginning of the list (the CAR of the list),
  • and make a recursive call on the rest (the CDR) of the list.