Lisp and Recursive Functions

Much of Lisp’s power and elegance lies in its recursive possibilities. Recursion can be found outside of Lisp, for example, as the mechanism generating the Fibonacci mathematical sequence. Each new number in this sequence is always the result from the addition of its two previous numbers. Given a seed of two numbers (1, 1), the recursive principle would generate the next five numbers as follows:


The same recursive process can be applied to collect the MIDI key numbers from
a list of events.

(defun collect-MIDI-notes (list-of-events)
 (if (null list-of-events) ()
 (cons (second (first list-of-events))
 (collect-MIDI-notes (rest list-of-events)))))

The program collect-MIDI-notes can be analyzed line by line as:

(defun collect-MIDI-notes (list-of-events)

Defining a new function called collect-MIDI-notes that accepts one argument, in this case:

a list-of-events.
(if (null list-of-events) ()

This line of code acts as a test that the program must perform each cycle in order to proceed. In this case it functions as a question for which the answer can either be true or false. The program asks: is this list-of-events empty? If that’s true, then stop, otherwise proceed with the following instructions.

(cons (second (first list-of-events))
 (collect-MIDI-notes (rest list-of-events))))

Construct a list with the value corresponding to the second atom from the first event in the list-of-events, while re-calling the function collect-MIDI-notes, this time, with all but the first event in the list-of-events. The process is then repeat, and “is the list-of-events empty?” is asked again. Since the function collect-MIDI-notes gets re-called each time with one less event in the list-of-events, inevitably there will be a moment where the list-of-events will be empty. When the function collect-MIDI-notes is re-called with an empty list, it will stop and return a list with all the collected notes:

(60 64 67 72)