Recursive Function Definitions

(the basic looping methodology)

LISP does not contain or support a mechanism that is equivalent to a looping construct in a Procedural (or Imperative) language, such as while-do or repeat-until. Consequently the repetition of a "block" of code must be accomplished by the use of RECURSION. This is implemented by defining a function that contains the code to be repeated and then having the function call itself. However such a simple construct would result in an infinite loop, so each recursive function must always contain two parts:

  1. Recursive call component(s), and
  2. At least one escape element that does not contain a reference to the function.**

Click here to evaluate the expression

(append '(A B) 'C)

The basic methodology of implementing LISP functions operating over lists using recursion is to operate on the CAR item non-recursively, and then over the CDR recursively. Look again at the above function definition to see this methodology. Here is another:

Given an atom A and a list of atoms LAT, determine whether A occurs in LAT:

(define MEMBER (A LAT)
        ((null LAT)   nil)
        ((eq A (car LAT))   t)
        (t   (MEMBER A (cdr LAT))) ) )

Reserved words (such as define, cdr, null, etc.) must be in lower case in our version; parameters or literals may be in upper or lower case, but are not interchangeable. That is (eq 'A 'a) will return nil (false).

** This must also preclude indirect recursion where a cycle of function calls eventually returns to the original function.


CS1104 Main Page
Last Updated 03/22/2000
© L.Heath, 2000, modified by J.A.N. Lee.