Algorithmic Composition: A Gentle Introduction to Music Composition Using Common LISP and Common Music
Skip other details (including permanent urls, DOI, citation information): This work is protected by copyright and may be linked to without seeking permission. Permission must be received for subsequent distribution in print or electronically. Please contact [email protected] for more information.
For more information, read Michigan Publishing's access and usage policy.
Chapter 13: Recursion
13.1 Introduction to Recursion
Recursion is something that is defined in terms of itself. A recursive function is a function that calls itself. A classic example of a recursive process is generating the Fibonacci series. In the Fibonacci series, the first two terms are defined as 0 and 1. Thereafter, the next term is calculated as the sum of the previous two terms. The mathematical relationship between terms may be stated as:
next-term = (term - 1) + (term - 2)
For example, the six terms followed by the initial two terms of 0 and 1 are:
0 1 1 2 3 5 8 13 . . .
Another example of a recursive process is decrementing a given starting value by 1 until it is equal to 0. We calculate the value of the next term as:
next-term = previous-term - 1
Given a starting value of 4, the resultant series is:
4 3 2 1
Perhaps the easiest way to begin writing recursive functions is to study recursive functions. After studying several examples, patterns emerge for different kinds of recursive conditions. This chapter introduces templates for recursion and gives examples of their use.
13.2 Single-Test Tail Recursion
Single-test tail recursion is a method of recursion when a condition terminates processing and the recursive function call occurs as the default case of a COND (e.g. the "tail end" of a COND ). Example 13.2.1 shows the template for single-test tail recursion.
Example 13.2.1: Template for Single-Test Tail Recursion
In addition to referencing a template when writing a recursive function, it is important to understand how a recursive process works. Example 13.2.2 outlines some guidelines for writing a recursive function.
Consider the example of decrementing a given number by one until it is equal to 0. For Let's say that our starting number is 4. Our recursive function should output the values 4, 3, 2, 1, and DONE as seen in Example 13.2.3.
Consider the guidelines for writing a recursive function in relation to Example 13.2.3. We stop the recursion when the number is equal to 0 so the END-TEST is (ZEROP X). Our recursive function returns DONE when it is completed so the END-VALUE is DONE. Each step in the process subtracts one from the previous term so the reduced-argument is (DECF X ).
Now that we've sketched some guidelines, we're ready to apply the template and write the function.
13.3 List-Consing Recursion
List-consing recursion is a recursive process that creates lists by consing a new element onto a list. Example 13.3.1 shows a template for list-consing recursion.
The function requires two inputs: a starting MIDI note value and the number of notes to generate. We stop the recursion after 6 notes have been generated. We need to decrement the number of notes generated until it is equal to zero. Our END-TEST is (ZEROP NUMBER-OF-NOTES). Our recursive function returns the completed list. Each step in the process is to subtract one from the number of notes and add one to the previous note. Example 13.3.2 is the solution.
Sometimes, adding a FORMAT statement to a recursive process helps clarify what it going on. Example 13.3.4 is the same function as 13.3.2 with a FORMAT statement prior to the recursive call.
13.4 Conditional Augmenting Tail Recursion
Conditional augmenting tail recursion is a function that conditionally increments a value or conses an element to a list. Example 13.4.1 shows the template for conditional augmenting tail recursion.
Example 13.4.1: Template for Conditional Augmenting Tail Recursion
Consider the example of counting the number of MIDI notes that exceed the range of the MIDI specification. Given the list of MIDI notes (87 67 129 776 43), the function should return 2.
The function requires two inputs: a list of MIDI notes and a variable to count the number of MIDI notes outside of the range. We stop the recursion when we reach the end of the list. Our END-TEST is (NULL THE-LIST). The recursive function returns the number of notes outside of the MIDI range. Each step in the process looks at the next element in the list by successively looking at the FIRST of the REST of the list. A solution is found in Example 13.4.2.
Example 13.4.2: recursive-count-outlyers.lisp
Sometimes, it is helpful to insert a FORMAT prior to the recursive call to track the changing values of the variables as seen in Example 13.4.4.
13.5 Double Test Tail Recursion
Double test tail recursion is a function that terminates based on one of two conditions. Example 13.5.1 shows the template for double test tail recursion.
Example 13.5.1: Template for Double Test Tail Recursion
Let's modify RECURSIVE-COUNT-OUTLYERS in Example 13.3.2 so that the function returns the first occurrence of a MIDI note number outside of the range of the MIDI Specification. Given the list of MIDI notes (87 67 129 776 43), the function should return 129. If no MIDI notes are outside the range of the MIDI Specification, the function returns NIL.
The function requires a list of MIDI notes as input. We stop recursion when we reach the end of the list. Recursive processing can also stop if we find a MIDI note outside of the range of the MIDI Specification. Since there are two ways that processing terminates, we have two end tests:(NULL MIDI-NOTE-LIST) and ((OR (< (FIRST MIDI-NOTE-LIST) 0) (> (FIRST MIDI-NOTE-LIST) 127)) (FIRST MIDI-NOTE-LIST)). That is why this technique is called double test tail recursion. Each step in the process is to look at the next element in the list that is done by successively looking at the FIRST of the REST of the list. A solution is found in Example 13.5.2.
Example 13.5.2: recursive-find-first-outly.lisp
As we saw before, it is helpful to insert a FORMAT prior to the recursive call. The modified function appears in Example 13.5.5.
13.6 Multiple Recursion
A function is categorized as multiple recursion if it makes more than one recursive call at each pass of the function. Generating the Fibonacci series requires multiple recursion because the next term is derived by the sum of the previous two terms (n - 2) + (n - 1). Example 13.6.1 shows the template for multiple recursion.
Example 13.6.1: Template for Multiple Recursion
The function requires a number as input that corresponds to the number of terms to generate. Two conditions terminate the recursion: when the input number is 0 and when it is equal to 1. These conditions allow us to return the first two terms. The default case of the COND establishes the relationship between terms by multiple recursion:(+ (FIBONACCI (- X 1)) (FIBONACCI (- X 2))). The function returns the specified number of terms beyond the initial term of 0. A solution is found in Example 13.6.2.
The output from multiple recursion can at first glance appear baffling. Common LISP uses stacks to process data. Figure 13.6.1 helps make sense of what LISP is doing when it is given the function call (FIBONACCI 5). The arrows indicate recursive calls. The squares containing either a 0 or 1 indicate when the input argument reaches 0 or 1 resulting in no further recursive calls. The circled numbers indicate the order in which the value of the input argument is printed.
Figure 13.6.1: Graphic representation of (FIBONACCI 5)
13.7 The LISP Debugger
Example 13.7.2 can be modified to use BREAK as seen in Example 13.7.2.
Example 13.7.2
BREAK places you in the Common LISP debugger. In the debugger, you can examine what LISP has placed on the stack using a stack backtrace. You can resume recursion by using continue. Backtrace and continue are implementation specific so consult your Common LISP manual for further information.
13.8 Using Recursive Forms in Common Music
Example 13.8.1 integrates many of the recursive techniques described in this chapter in Common Music. The function RECURSIVE-MAKE-A-CHROMATIC-LICK uses list-consing recursion to generate a specified number of chromatic notes. The function RANGE-LIMITED-RANDOM-NUMBERS uses tail recursion to generate a specified number of random numbers is a user-specified range. The function COUNT-IN-RANGE uses conditional augmenting tail recursion to count the number of notes that fall within a user-specified range (lower and upper bound inclusive).
These Common LISP functions are used in the generator recursion-etude. The function RECURSIVE-MAKE-A-CHROMATIC-LICK is used to generate the note information, create an item stream, and assign the item stream to the variable note-list. The function RANGE-LIMITED-RANDOM-NUMBERS is used to generate a list of 15 random numbers in the range .25 to .98. The list is assigned to the variable RHYS THAT is used to create a cyclic item stream called rhy-list. The variable RHYS is used as input to the function COUNT-IN-RANGE as we look for values between .5 and .8 inclusive. The function returns a number that is used in calculating the value of the amplitude slot.
Example 13.8.1: recursion-etude.lisp
recursion-etude.mp3
13.9 Suggested Listening
On Growth and Form by Bruno Degazio for mixed ensemble and electronic sounds explores the recursive structure of fractals. As the composer states, "Drawing on the chaotic energy of fractal processes, On Growth and Form is a sort of ritual dance of life, the by-product of a recursive explosion of musical events." [Degazio, 1992]
Profile for tape by Charles Dodge is a three-voice composition in which the choice of pitch, timing, and amplitude is determined by application of a 1/f algorithm. The structure of the work is like a fractal in that recursive processes are used to determine multiple levels of scale and self-similarity. [Dodge, 1988]
