Previous | Table of Contents | Next |
6.3.1.2. Recursive Generators
Recursion is a powerful tool for formulating solutions to problems that are defined in self-referential ways. Recurrences such as the ones for factorials, the triangular numbers, and the Fibonacci numbers given earlier provide simple examples. Such formulations are easily cast in terms of recursive procedures.
Procedures also can be recursive generatorssuspending with calls of themselves either directly or through a chain of other procedure calls.
Because few programming languages support generators, the concept of recursive generation may seem strange, and it may be difficult initially to understand what is going on or how to use it. Examples follow.
Recursive generators often arise naturally for computations that have more than one value. Consider the permutations of a stringthe different ways in which the characters of a string can be rearranged. For example, the permutations of abc are
abc acb bac bca cab cba
In general, there are n! permutations of an n-character string.
The obvious approach to producing the permutations of a string is to extract each character and concatenate it with the permutations of the remaining characters. Thus, the preceding permutations can be constructed from
a || permute(bc) b || permute(ac) c || permute(ab)
where permute(s) produces (generates) the permutations of s. The step to recursion is clear, and is easily formulated as a recursive generator:
procedure permute(s) if *s = 0 the return every i := 1 to *s do suspend s[i] || permute(s01:i] || s[i+1:0]]) end
The test for an empty string provides termination for the recursion. (The empty string, by convention, has only itself as a permutation.)
Another example of the utility of recursive generation is the closure of a set of characters: all the strings that can be composed from the characters, given in order of increasing length. For example, the closure of abc is , a, b, c, aa, ab, ac, ba, . A procedure that generates the closure of a set of characters is
procedure closure(c) suspend | (closure(c) || !c) end
In order to understand the sequence of results for this procedure, consider
closure(abc)
The first value is the empty string, produced by suspending with . The subsequent values consist of each value in the sequence produced by closure(abc) concatenated with each character in abc. Because !c is repeatedly resumed for each value generated by closure(c), each character in c is appended to the first value in the results for closure(c). Therefore, the results are , a, b, c, . When closure(c) is resumed for its second result, it produces a, onto which are appended in succession a, b, and c, and so on.
Recursive generators also can be used to generate the sequences for many recursively defined functions. For example, the Fibonacci numbers are generated by fibseq(1, 1) using the following procedure:
procedure fibseq(i, j) suspend i | fibseq(j, i + j) end
Other examples of recursive generators are noted in subsequent sections.
Previous | Table of Contents | Next |