LISP

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.**

• Let us define a new function that is like cons but which appends the second argument to the end of the list in the first argument:

(define append (x y)
(cond

( (= '() x) (cons y '()))
(t (cons (car x) (append (cdr x) y)))

)
)

• where "t" is the predefined constant with the value "true". This is equivalent to an "otherwise" condition.

• For "safety" every cond statement should have an otherwise clause.

• NOTE: every recursive definition contains at least one option that does not involve the recursive function call.

`(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)
(cond
((null LAT)   nil)
((eq A (car LAT))   t)
(t   (MEMBER A (cdr LAT))) ) )
```

 CAVEAT EMPTORReserved 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.