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.

© Charles Ames | Page created: 2017-03-12 | Last updated: 2017-03-12 |