Chapter 10
Recursion

The typescript for chapter 10 is provided in AutomatedComposition10.pdf.

This chapter introduces the concept of recursion in general, leaving musical applications for later. The typescript defines a process to be recursive if it is capable of acting upon its own results. However, what this chapter is really trying to get to are processes which branch out geometrically. One example is algebraic parsing, where complex expressions are broken down into progressively simpler sub-expressions and ultimately into discrete operations of addition, subtraction, multiplication, division, and so forth. Another example is fractal generation, where simple rules are used to elaborate an abstract form into component sub-forms, where the same rules are used to elaborate the sub-forms, and so on, going down many levels.

The discussion of mathematical recursion ought to have cited examples such as the Cantor set, the Peano curve, the Koch snowflake, and the Weierstrass function; instead it concentrates upon constructs more properly characterized as inductive, such as Peano's whole-number axioms.

A discussion of self-invoking programs is illustrated first by a program for generating Fibonacci numbers. and second by a program enumerating all the ways of choosing three items out of seven. The purpose here is to show that what can be achieved by a subroutine that references itself can also be achieved without self reference, by pushing variables onto an explicit stack before moving on to sub tasks, and by popping variables off the stack when a sub task has run to completion.

The chapter cites generating Fibonacci numbers as an example of horizontal or left-to-right recursion, which terminates upon reaching a goal level. By contrast, the chapter cites choosing three items out of seven as an example of vertical or top-down recursion, which terminates upon returning to the original level. horizontal recursion is implemented using a queue, while vertical recursion is implemented using a stack. A section explaining queues is illustrated by an eighth-order Markov chain. A section explaining stacks is illustrated by the mechanics of partition/exchange sorting.