LEARNING LISP

Contents | The Conditional | The Lisp Editor ED

Simple Recursion

Recursion occurs when a program calls itself as a help function. How can a function be defined in terms of itself? That sounds like a circular definition!

Recursion avoids circularity by defining the function in terms of simpler cases of itself. If we keep using the function on simpler cases, then eventually the function will get to a simple enough case and as such will know the answer without having to recur.

Let's try a simple program, called RECITE, to print out all the elements in a list with one element per line of output. We will do this by having our function print out the CAR of the list, using the built-in Lisp function PRINT, and then call itself, recur with the CDR of the list. Notice that because we are going to pass the CDR of the list, the list will get smaller with each recursive call.

Recursion is useless unless we can make it stop. RECITE, therefore, should do the following: If its argument is NIL, then it should return to NIL. [This type of test is called a termination condition. We need it to keep List from running away.] If its argument is not a NIL, then print the CAR of the argument and call RECITE again with the CDR. Here is RECITE.

:(DEFINE (RECITE (LAMBDA (STUFF)

:   (COND ((NULL STUFF) ())

:         (T (PRINT (CAR STUFF))

:            (RECITE (CDR STUFF)))

:     ))))

  RECITE

:(RECITE '(THIS IS A TEST LIST))
  THIS
  IS
  A
  TEST
  LIST

  NIL
When STUFF is NIL, the COND evaluates "(null stuff)" to T and evaluates the "()" as dictated by COND. Otherwise it prints the CAR of the list and calls RECITE, binding the CDR of STUFF to the new STUFF. Notice that it does not replace the value of STUFF but simply binds a new local value to it. When that particular call terminates, the previous value of STUFF will return. The NIL displayed at the end is not printed by the PRINT function. Rather, it is the value returned by the RECITE function. It came from the succession of recursive function terminations. When the function we started off with terminates, it prints out its value because there is no "caller" to return to other than the user.

What would have happened if we had left out the termination condition? Answer: no end in sight.

:(DEFINE (RECITE (LAMBDA (STUFF)

:   (PRINT (CAR STUFF))

:   (RECITE (CDR STUFF)))))))

  RECITE

:(RECITE '(THIS IS A TEST))
  THIS
  IS
  A
  TEST
  NIL
  NIL
  NIL
  NIL
  NIL
  NIL

+()

  NIL
{We hit control C.}

The list of NILs in the above execution will go on forever. We've cut off at seven in order to preserve our forests. This is a good time to learn about how to do that--that is, stop a function that is running wild. The answer is control-C. When a Lisp function starts repeating, you simply hold CONTROL and hit C. This causes Lisp to break the function, suspend it, and enter the "+" mode. [We've talked about this before.]

Onward to another example. The function we are going to define is called MEMBER. This function will take two arguments, an atom and a list. MEMBER will return a T if the atom is one of the top-level elements of the list, NIL otherwise. We now exhibit the function definition and some examples of its uses.

:(DEFINE (MEMBER (LAMBDA (A L)

:        (COND

:          ((NULL L) NIL)

:            ((EQUAL A (CAR L)) T)

:            (T (MEMBER A (CDR L)))))))

  MEMBER

:(MEMBER 'MAN '(UNION MAN))

  T

:(MEMBER 'SNURD '(ELMER SNERD))

  NIL

:(MEMBER 'A '((A B) C D))

  NIL
Here, we first test to see if L is an empty list. If it is, we need to search no further. We then compare the specified atom A with the first element of list L. If they are equal, then we have a match and the value of T is returned. Otherwise, we try again, looking for the atom in the CDR of the list. Note that this process is guaranteed to terminate because the function either returns a value or tries again with a shorter list. A list can only contain a finite number of elements so that after a maximum number of calls equal to the number of top-level elements in the initial list, we must reach an answer.

Let's follow the MEMBER function with a debugging tool called TRACE. The Lisp TRACE function will tell us who calls whom and what is returned. When you see "-->>", it means that the function is being called. When you see "<<--", it indicates that the function is returning. Follow these examples and watch what's happening. Note that you get an extra set of parentheses around the arguments in the "-->>" trace.

:(TRACE MEMBER)

  T

:(MEMBER 'ARM '(HEAD LEG ARM FOOT))

   -->> MEMBER :: (ARM (HEAD LEG ARM FOOT))
   -->> MEMBER :: (ARM (LEG ARM FOOT))
   -->> MEMBER :: (ARM (ARM FOOT))
   <<-- MEMBER :: T
   <<-- MEMBER :: T
   <<-- MEMBER :: T
Note that the "T" result is passed back through each level of the recursive call. It isn't just popped right back up to the top from the last call [the last "-->>"].

Let's try one that fails [returns NIL].

:(MEMBER 'HAND '(ARM HEAD LEG FOOT))
     ->> MEMBER :: (HAND (ARM HEAD LEG
     FOOT ) )
     ->> MEMBER :: (HAND (HEAD LEG FOOT )
     )
     ->> MEMBER :: (HAND (LEG FOOT ) )
     ->> MEMBER :: (HAND (FOOT ) )
     ->> MEMBER :: (HAND NIL )
     <<- MEMBER :: NIL
     <<- MEMBER :: NIL
     <<- MEMBER :: NIL
     <<- MEMBER :: NIL
     <<- MEMBER :: NIL

  NIL
The same returning sequence happens with the NIL. In fact, the same type of thing will always happen in a Lisp function that returns the values to the routine that called it, never back to the user directly. We saw this in the ENDS example and it also applies to recursion.

The opposite of TRACE is UNTRACE.

:(UNTRACE MEMBER)

  NIL
If you forget to UNTRACE your functions they will keep tracing themselves until you either restart Lisp, or shut off your computer.

If you wish to turn tracing off of all of your functions at once, simply type (UNTRACE).

:(UNTRACE)

  NIL
As a third example, we will look at a recursive mathematical function, namely, the factorial. Recall that the factorial of n is the product of the first n integers and is defined by the following recursive formula:
n! = 1            if n = 0
    n*(n-1)!      if n > 0
Notice that the termination condition is already specified in the definition, namely, that the recursion stops when n=0. The factorial can easily be defined in Lisp, as follows:
:

:(DEFINE (FACTORIAL (LAMBDA (N)

:   (COND

:   ((EQUAL N 0) 1)

:   (T (MULT N (FACTORIAL (SUB N 1))))

:   ))))

  FACTORIAL

:(FACTORIAL 0)

  1

:(FACTORIAL 1)

  1

:(FACTORIAL 2)

  2

:(FACTORIAL 3)

  6

:(FACTORIAL 5)

  120
It would be instructive to trace an evaluation of FACTORIAL to see how it works. Here's a trace of (FACTORIAL 5).
:(FACTORIAL 5)
     ->> FACTORIAL :: (5 )
     ->> FACTORIAL :: (4 )
     ->> FACTORIAL :: (3 )
     ->> FACTORIAL :: (2 )
     ->> FACTORIAL :: (1 )
     ->> FACTORIAL :: (0 )
     <<- FACTORIAL :: 1
     <<- FACTORIAL :: 1
     <<- FACTORIAL :: 2
     <<- FACTORIAL :: 6
     <<- FACTORIAL :: 24
     <<- FACTORIAL :: 120

  120
Notice how each value of FACTORIAL is passed back through every level of the recursive call, where it is multiplied by the value of n at that level. Work through the example to be sure you understand it.

Exercises

  1. Write a recursive function that adds up the numbers in a list, for example (1 2 3 4) = 10.
  2. Write a recursive function that takes a list and returns everything minus the last element.

Answers

  1. (DEFINE (SUM (LAMBDA (L)
       (COND
          ((NULL L) 0)
          (T (ADD (CAR L) (SUM (CDR L))))
       )
    )))
    
  2. (DEFINE (RDC (LAMBDA (L)
       (COND
        ((NULL (CDR L)) NIL)
        (T (CONS (CAR L) (RDC (CDR L))))
       )
    )))
    

Contents | The Conditional | The Lisp Editor ED