Algorithmic Composition: A Guide to Composing Music with Nyquist

Chapter 11. Recursion

132 Chapter 11 Recursion Recursion is an important concept in computer science. In this chapter, we will explore what it means for a function to call itself and why that might be a good idea. 11.1 Introduction to Recursion Recursion occurs when something refers to itself. For example, a recursive definition uses the term being defined within the definition. 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 = current-term + previous-term 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 = current-term – 1 Given a starting value of 4, the resultant series is 4 3 2 1 Notice in both cases, recursion reduces the current problem to a simpler one that can be solved by the same function (with different inputs). Typically, the process eventually terminates in a special case. (The second example terminates at zero.) 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. 11.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 11.2 Single-Test Tail Recursion 133 default case of an if-then-else statement (e.g. the “tail end” of an ifthen -else). Example 11.2.1 shows the template for single-test tail recursion . Example 11.2.1: Template for single-test tail recursion define function function-name(input) begin if end-test then return end-value else return function-name(reduced-input) end In addition to referencing a template when writing a recursive function , it is important to understand how a recursive process works. Here are some 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-input) Consider the example of decrementing a given number by 1 until it is equal to 0. 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 11.2.2. Example 11.2.2: Recursive function output 4 3 2 1 DONE Consider the guidelines for writing a recursive function in relation to this output. We stop the recursion when the number is equal to 0 so the end-test is x = 0. Our recursive function returns done when it is completed so the end-value is quote(done). Each step in the process subtracts one from the previous term so the reduced-input is x - 1. Now that we’ve sketched some guidelines, we’re ready to apply the template and write the function. 134 Chapter 11 ⋅ Recursion Example 11.2.3: recursive-dotimes.sal define function recursive-dotimes(x) begin if x = 0 then return quote(done) else begin print x return recursive-dotimes(x - 1) end end Example 11.2.4: Output from recursive-dotimes SAL> load "recursive-dotimes.sal" SAL> exec recursive-dotimes(4) 4 3 2 1 DONE 11.3 List-Cons’ing Recursion List-cons’ing recursion is a recursive process that creates lists by cons’ing a new element onto a list. Example 11.3.1 shows a template for list-cons’ing recursion. Example 11.3.1: Template for list-cons’ing recursion define function function-name(inputs) begin if end-test then return nil ; return the empty list else return cons(new-element, function-name(reduced-inputs)) end 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...