Lab 11: Generative recursion 1

Remember to follow (and when necessary, adapt) the design recipe for each function. When you write a generative recursive function, you must provide a termination argument.

1 Power

As you saw in Lecture 22: Merge sort, creatively decomposing problems can make them faster to solve. In this section, you’ll apply this lesson to a different problem: raising a given number to a given power. First you’ll use structural recursion to design a slow solution to the problem; then you’ll use generative recursion to design a fast solution to the problem.

Exercise 2. A typical bank account yields 0.01% interest per day. In such an account, how much money does $1 become in 10,000 days? Compute the answer by running (power 1.0001 10000). How long does the computation take? (You can measure how long it takes using time.)

Exercise 3. Because you designed power by following the template for processing a NaturalNumber, it decomposes the problem (power 1.0001 10000) into the problem (power 1.0001 9999). We can make power faster by decomposing the exponent 10000 differently, into the exponent 5000 instead of 9999. After all, the answer to (power 1.0001 10000) is simply the square of the answer to (power 1.0001 5000).

Exercise 4. Design a function power-tree-result that takes a number x and a PowerTree pt and returns the number that is x raised to the (power-tree-exponent pt)-th power. But do not use the slow power function you designed, and do not use any built-in function for exponentiation either. Instead, follow the template for processing a PowerTree.

In order to fill in the template and complete the definition, you need to turn the recursion outcomes provided by the template into the expected output, so make sure you write enough examples, and perhaps use the table method. For example, to handle the input pt = (generate-power-tree 9), you need to turn the recursion outcome x8 into the expected output x9, by multiplying by x. And to handle the input pt = (generate-power-tree 8), you need to turn the recursion outcome x4 into the expected output x8, by squaring. In general, you need to use the equation x2n = (xn)2.

Because this function follows a processing template, you can be sure that it always terminates, and you do not need to write any termination argument.

Exercise 5. Combine generate-power-tree and power-tree-result to design a function fast-power like power: it takes a number x and a natural number n and returns the number that is x raised to the n-th power. The definition of fast-power is very short, does not use recursion, and can be written just by looking at the signatures of generate-power-tree and power-tree-result. Your fast-power should pass the same tests as power above. Again, do not use the slow power function you designed, and do not use any built-in function for exponentiation either.

Exercise 6. Compute the same answer as Exercise 6 by running (fast-power 1.0001 10000). How long does the computation take? (You can measure how long it takes using time.)

2 DNA compression

DNA is often modeled by strings of the characters A, C, G and T. They are very long and so often need to be compressed. A simple way to do this is run-length encoding. It means to replace all substrings of identical consecutive characters with the character followed by the length of the substring. These substrings must be as long as possible. For example, the run-length encoding of the string "AAAAAAAAAAGCCCCC" is the string "A10G1C5". This is the only run-length encoding—something like "A4A6G1C5" is not valid.

3 DNA decompression

The goal of this section is to convert run-length encodings back to DNA strings. For example, we want to convert the run-length encoding "A10G1C5" back to the DNA string "AAAAAAAAAAGCCCCC", and we want to convert the empty run-length encoding "" back to the empty DNA string "". To achieve this goal, decompose the problem via the same DNATree as defined above.