Sunday, 16 May 2010

Yet More Recursion in Lisp

Our last Lisp tutorial looked at using recursion to access data from nested lists. Today's Lisp tutorial looks at more Lisp recursion techniques. Firstly let's look at the Lisp Programming Challenge from our last Lisp recursion post:

(defun get-orbit (planet-list)
  (if (null planet-list) nil
    (cons (second (first planet-list))
          (get-orbit (rest planet-list)))))

(defun get-diameter (planet-list)
  (if (null planet-list) nil
    (cons (third (first planet-list))
          (get-diameter (rest planet-list)))))

(defun get-mass (planet-list)
  (if (null planet-list) nil
    (cons (fourth (first planet-list))
          (get-mass (rest planet-list)))))

More Recursion in Lisp
There are certain functions that we usually apply to numbers and cannot apply to lists for example:
(/ 8 2)
4

Whereas the following will create an error:
(/9 '(2 3 4))

If, as in the above example, we wanted to divide a list of numbers by another number we could write a recursive function to do this:

(defun divide-list-by-x (the-list x) 
    (if (null the-list) nil      
      (cons (/ (first the-list) x)     
      (divide-list-by-x (rest the-list) x))))

(divide-list-by-x '(2 3 4) 2)
(1 3/2 2)

Similarly we could write a recursive Lisp function to perform the modulus function on a list of numbers:

(defun list-mod (the-list mod)
         (if (null the-list) nil
           (cons (mod (first the-list) mod)
                 (list-mod (rest the-list) mod))))

 When writing recursive Lisp functions we need to be able to define the following 3 things:

    * When to stop recursing
    * How do we take the next step
    * How to call the recursive function

The two recursive Lisp examples above use a single test to identify when to stop recursing, however we can also use two (or more) tests to identify when the recursive function should stop. In this example, we check to see if a given number is less than every number in a list by writing a recursive function. The function stops recursing if it reaches the end of the list, or if the function encounters a number that is equal to or greater than our test number:

(defun less-than-list (x the-list) 
   (cond ((null the-list) t)       
             ((>= x (first the-list)) nil)       
             (t (less-than-list x (rest the-list)))))

Today's Programming Lisp Challenge

Lisp has many different data types. Write a function to extract the numbers from this list:

(1 Partridge 2 Turtle Doves 3 French Hens 4 Calling Birds 5 Gold Rings)

So:
(extract-numbers '(1 Partridge 2 Turtle Doves 3 French Hens 4 Calling Birds 5 Gold Rings))

should return:

(1 2 3 4 5)

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