Lisp Recursion Tutorial | Recursion in Lisp

Today's Programming Lisp tutorial looks at recursion. Recursion is a very powerful programming tool in Lisp, but before we being let's have a look at the answer to the last programming lisp challenge.

Write a function called BETWEEN that takes 3 input arguments N, MIN and MAX. This function tests to see if N is between MIN and MAX.

(defun between (n min max)
  (if (and (>= n min)
           (<= n max)) t nil))

And with some example input:

(between 6 3 9)
T

(between 2 3 9)
NIL

Recursion in Lisp
Recursion is when a function calls itself. The best way to introduce it is to look at some examples. we've looked at predicates before: the ODDP predicate tests to see if a number is odd however this predicate only works with numbers and not lists. We can use a recursive function (a function that calls itself) to see if there are any odd numbers in the list.

(defun any-odd (the-list)
                  (cond ((null the-list) nil)
                        ((oddp (first the-list)) t)
                         (t (any-odd (rest the-list)))))


The above function illustrates some important features of programming recursive features, here's a line by line break down:

this line defines the function's name as any-odd and its input as the-list:

(defun any-odd (the-list)

This line uses COND to setup a conditional test, (null the-list) checks to see if we're reached the end of the list, if we have it returns nil, if not we go on to the next line of our conditional statement:

(cond ((null the-list) nil)

This line takes the first item of the-list and uses this as the input to ODDP, if ODDP is true we return T:

((oddp (first the-list)) t)

The final line is only evaluated if the previous lines evaluated to nil. This is were the function becomes recursive - it calls itself. Our ANY-ODD function is called with the REST of the list. 

(t (any-odd (rest the-list)))))

Here's another example, this time we'll take a number and a list as input, and check to see if the number appears in the list:

(defun n-in-list (n the-list)
                      (cond ((null the-list) nil)
                        ((equalp n (first the-list)) t)
                         (t (n-in-list n (rest the-list)))))

When programming recursive functions in Lisp we have to know:

• When to stop recursing - in both of the above examples we return nil when we reach the end of the list (null the-list)
• How do we take the next step? This is usually the body of the recursive function. In our ANY-ODD function our step was to test the first item of the list to see if it was ODD, in our N-IN-LIST function, our step was to use the EQUALP predicate and see if N was equal to the FIRST element of the-list
• How to call the recursive function? In the ANY-ODD function above, the function calls itself with the REST of the list. With the N-IN-LIST function, the function calls itself with N and the REST of the-list.

Today's Programming Lisp Challenge
Write a function called INCREASING-P this function returns T if all the numbers in the list are in ascending order and NIL if they are not.

Subscribe to the RSS feed and check back soon for the answer and more Programming Lisp tutorials.