spobooksbbv9810.0001.001 in

    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

    (DEFUN FUNCTION-NAME (ARGUMENT)
    (COND (END-TEST END-VALUE)
    (T (FUNCTION-NAME (REDUCED ARGUMENT)))))

    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.

    Example 13.2.2: Guidelines for Writing a Recursive Function
    1. What is the test that terminates the recursion? (e.g. end-test)
    2. What do you want the function to return? (e.g. end-value)
    3. How do you take one step? (e.g. reduced-argument)

    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.

    Example 13.2.3
    4
    3
    2
    1
    DONE

    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.

    Example 13.2.4: recursive-dotimes.lisp
    (defun recursive-dotimes (x)
    (cond ((zerop x) 'done)
    (t (print x) (recursive-dotimes (decf x)))))
    Example 13.2.5: Output from Example 13.2.4
    ? (recursive-dotimes 4)
    4
    3
    2
    1
    DONE

    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.

    Example 13.3.1: Template for List-Consing Recursion
    (DEFUN FUNCTION-NAME (ARGUMENT)
    (COND (END-TEST NIL)
    (T (CONS NEW-ELEMENT(FUNCTION-NAME REDUCED-ARGUMENT)))))
    Consider the example of creating a list that starts at a particular value and ends after a certain number of elements have been generated. For example, we want to write a function that starts at MIDI note 60 and generates a list of 6 notes that ascend chromatically. Our recursive function should return:
    (60 61 62 63 64 65)

    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.

    Example 13.3.2: recursive-make-chromatic-lick.lisp
    (DEFUN RECURSIVE-MAKE-A-CHROMATIC-LICK(START NUMBER-OF-NOTES)
    (COND ((ZEROP NUMBER-OF-NOTES) NIL)
    (T (CONS START
    (RECURSIVE-MAKE-A-CHROMATIC-LICK (+ START 1)(- NUMBER-OF-NOTES 1))))))
    Example 13.3.3: Output from Example 13.3.2
    ? (recursive-make-a-chromatic-lick 60 6)
    (60 61 62 63 64 65)

    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.

    Example 13.3.4: recursive-make-a-chromatic-lick.lisp
    (defun recursive-make-a-chromatic-lick (start number-of-notes)
    (cond ((zerop number-of-notes) nil)
    (t (format t "~&start = ~A number-of-notes = ~A" start number-of-notes) (cons start
    (recursive-make-a-chromatic-lick (incf start)
    (decf number-of-notes))))))
    Example 13.3.5: Output from Example 13.3.4
    ? (recursive-make-a-chromatic-lick 60 6)
    start = 60 number-of-notes = 6
    start = 61 number-of-notes = 5
    start = 62 number-of-notes = 4
    start = 63 number-of-notes = 3
    start = 64 number-of-notes = 2
    start = 65 number-of-notes = 1
    (60 61 62 63 64 65)

    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

    (DEFUN FUNCTION-NAME (ARGUMENT)
    (COND (END-TEST END-VALUE)
    (AUGMENT-CONDITION (AUGMENT-FUNCTION AUGMENT-VALUE (FUNCTION-NAME REDUCED-ARGUMENT)))
    (T (FUNCTION-NAME REDUCED-ARGUMENT))))

    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

    (defun recursive-count-outlyers (the-list result)
    (cond ((null the-list) result)
    ((or
    (< (first the-list) 0)
    (> (first the-list) 127))
    (incf result)
    (format t "~%result = ~a the-list = ~a" result the-list)
    (recursive-count-outlyers (rest the-list) result))
    (t (recursive-count-outlyers (rest the-list) result))))
    Example 13.4.3: Output from Example 13.4.2
    ? (recursive-count-outlyers
    '(87 67 129 776 43) 0)
    2

    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.

    Example 13.4.4
    (defun recursive-count-outlyers (the-list result)
    (cond ((null the-list) result)
    ((or
    (< (first the-list) 0)
    (> (first the-list) 127))
    (incf result)
    (format t "~%result = ~a the-list = ~a" result the-list)
    (recursive-count-outlyers (rest the-list) result))
    (t (format t "~%result = ~a the-list = ~a" result the-list) (recursive-count-outlyers
    (rest the-list) result))))
    Example 13.4.5: Output from Example 13.4.4
    ? (recursive-count-outlyers
    '(87 67 129 776 43) 0)
    result = 0 the-list = (87 67 129 776 43)
    result = 0 the-list = (67 129 776 43)
    result = 1 the-list = (129 776 43)
    result = 2 the-list = (776 43)
    result = 2 the-list = (43)
    2

    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

    (DEFUN FUNCTION-NAME (ARGUMENT)
    (COND (END-TEST1 END-VALUE1)
    (END-TEST2 END-VALUE2)
    (T (FUNCTION-NAME REDUCED-ARGUMENT))))

    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

    (defun recursive-find-first-outlyer (midi-note-list)
    (cond ((null midi-note-list) nil)
    ((or (< (first midi-note-list) 0)
    (> (first midi-note-list) 127))
    (first midi-note-list))
    (t (recursive-find-first-outlyer
    (rest midi-note-list)))))
    Example 13.5.3: Output from Example 13.5.2
    ? (recursive-find-first-outlyer '(87 67 129 776 43))
    129

    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.

    Example 13.5.5: recursive-find-first-outlyer.lisp
    (defun recursive-find-first-outlyer (midi-note-list)
    (cond ((null midi-note-list) nil)
    ((or (< (first midi-note-list) 0)
    (> (first midi-note-list) 127))
    (first midi-note-list))
    (t (format t "~&midi-note-list = ~a"
    midi-note-list) (recursive-find-first-outlyer
    (rest midi-note-list)))))
    Example 13.5.6: Output from Example 13.5.5
    ? (recursive-find-first-outlyer '(87 67 129 776 43))
    midi-note-list = (87 67 129 776 43)
    midi-note-list = (67 129 776 43)
    129

    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

    (DEFUN FUNCTION-NAME (ARGUMENT)
    (COND (END-TEST1 END-VALUE1)
    (END-TEST2 END-VALUE2)
    (T (COMBINER(FUNCTION-NAME FIRST-REDUCED-ARGUMENT)
    (FUNCTION-NAMESECOND-REDUCED-ARGUMENT)))))

    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.

    Example 13.6.2: fibonacci.lisp
    (defun fibonacci (x)
    (format t "~&x = ~s" x)
    (cond ((zerop x) 0)
    ((= x 1) 1)
    (t (+ (fibonacci (- x 1)) (fibonacci (- x 2))))))
    Example 13.6.3: Output from Example 13.6.2
    ? (fibonacci 5)
    x = 5
    x = 4
    x = 3
    x = 2
    x = 1
    x = 0
    x = 1
    x = 2
    x = 1
    x = 0
    x = 3
    x = 2
    x = 1
    x = 0
    x = 1
    5

    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

    Up to this point, we have tried to stay out of the debugger. The debugger can be a helpful place to learn how Common LISP handles things. To invoke the debugger, use the Common LISP BREAK function. The template for the BREAK function is:
    (BREAK "OPTIONAL STRING")

    Example 13.7.2 can be modified to use BREAK as seen in Example 13.7.2.

    Example 13.7.2

    (defun fibonacci (x)
    (cond ((zerop x) 0)
    ((= x 1) 1)
    (t (break "right before a recursive call")
    (+ (fibonacci (- x 1))
    (fibonacci (- x 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

    #|
    Make a chromatic lick for note events
    |#
    (defun recursive-make-a-chromatic-lick (start number-of-notes)
    (cond ((zerop number-of-notes) nil)
    (t (cons start (recursive-make-a-chromatic-lick
    (incf start) (decf number-of-notes))))))
    #|
    Define a recursive function range-limited-numbers that generates a prescribed number of random values in a user-specified range
    |#
    (defun range-limited-random-numbers
    (lower-bound upper-bound how-many)
    (cond ((zerop how-many) nil)
    (t (cons (+ (random (- upper-bound lower-bound))
    lower-bound) (range-limited-random-numbers
    lower-bound upper-bound (decf how-many))))))
    #|
    Define a recursive function count-in-range that returns how many elements in a list are inside of user-specified range (lower and upper bound inclusive).
    |#
    (defun count-in-range (the-list lower-bound upper-bound result)
    (cond ((null the-list) result)
    ((and
    (>= (first the-list) lower-bound)
    (<= (first the-list) upper-bound))
    (incf result)
    (count-in-range (rest the-list)
    lower-bound upper-bound result))
    (t (count-in-range (rest the-list)
    upper-bound lower-bound result))))

    audio file recursion-etude.mp3

    #|
    Create a generator called recursion-etude that uses the three recursive functions: make-a-chromatic-lick.lisp, range-limited-random-numbers, and count-in-range. These three functions highlight three recursive processes: list consing recursion, single-test tail recursion, and conditional augmenting tail recursion.
    #|
    (generator recursion-etude midi-note (channel 0 length 15)
    (vars (note-list (make-item-stream 'items 'heap
    (recursive-make-a-chromatic-lick 60 12)))
    (rhys (range-limited-random-numbers .25 .98 15))
    (rhy-list (make-item-stream 'items 'cycle rhys))
    (amps (count-in-range rhys .5 .8 0)))
    (setf note (item note-list))
    (setf rhythm (item rhy-list))
    (setf amplitude (* (random amps) .1))
    (setf duration rhythm))

    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]