On this page:
1 Power
2 DNA compression
3 DNA decompression
8.5

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 1. Design a function power that takes a number x and a natural number n and returns the number that is x raised to the n-th power. Here n is the exponent. Do not use any built-in function for exponentiation.
(check-expect (power 10 3) 1000)
(check-expect (power 2 10) 1024)
(check-expect (power 1.1 4) 1.4641)
Hint: Do not use generative recursion; this exercise is just to warm up. Instead, stick with structural recursion and follow the template for processing a NaturalNumber:
; A NaturalNumber is one of:
; - 0
; - (+ 1 NaturalNumber)

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).

In general, let’s decompose a NaturalNumber into a PowerTree defined below:
; A PowerTree is one of:
; - (make-zeroth)
; - (make-oddth  PowerTree)
; - (make-eventh PowerTree)
(define-struct zeroth [])
(define-struct oddth  [sub1])
(define-struct eventh [half])
The interpretation of a PowerTree is specified by the following function.
; power-tree-exponent : PowerTree -> NaturalNumber
; returns the meaning of the given PowerTree
(define (power-tree-exponent pt)
  (cond [(zeroth? pt) 0]
        [(oddth?  pt) (+ 1 (power-tree-exponent (oddth-sub1  pt)))]
        [(eventh? pt) (* 2 (power-tree-exponent (eventh-half pt)))]))

Design a function generate-power-tree that takes a natural number and decomposes it into a PowerTree whose interpretation is it. For example, (generate-power-tree 10000) should generate a PowerTree whose interpretation is 10000.
(check-expect (power-tree-exponent (generate-power-tree 10000)) 10000)
To keep the generated PowerTree as small as possible, do not follow the structural recursion template for processing a NaturalNumber. Instead, check if the input is zero, odd, or even.
  • If the input is zero, then just return (make-zeroth) because its interpretation is zero.

  • If the input is odd, then make a recursive call on a natural number that is one less.

  • If the input is even, then make a recursive call on a natural number that is half.

Because this function makes recursive calls without following any processing template, you must remember to make it terminate, and write a termination argument that explains why the function eventually stops; it is not enough to say only when the function stops. Your definition of generate-power-tree should pass these tests:
(check-expect (generate-power-tree 0)
              (make-zeroth))
(check-expect (generate-power-tree 1)
              (make-oddth (make-zeroth)))
(check-expect (generate-power-tree 2)
              (make-eventh (make-oddth (make-zeroth))))
(check-expect (generate-power-tree 4)
              (make-eventh (make-eventh (make-oddth (make-zeroth)))))
(check-expect (generate-power-tree 8)
              (make-eventh (make-eventh
               (make-eventh (make-oddth (make-zeroth))))))
(check-expect (generate-power-tree 9)
              (make-oddth (make-eventh (make-eventh
               (make-eventh (make-oddth (make-zeroth)))))))

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.

The goal of this section is to convert DNA strings to run-length encodings. For example, we want to convert the DNA string "AAAAAAAAAAGCCCCC" to the run-length encoding "A10G1C5", and we want to convert the empty DNA string "" to the empty run-length encoding "". To achieve this goal, decompose the problem via a DNATree defined below:
; A DNATree is one of:
; - (make-end)
; - (make-run 1String NaturalNumber DNATree)
(define-struct end [])
(define-struct run [base count rest])

Exercise 7. Design a function generate-encoding that takes a DNA string as input and decomposes its encoding problem into a DNATree. Assume that the given DNA string will only consist of upper-case A, C, G and T. Here are two examples:
(check-expect (generate-encoding "AAAAAAAAAAGCCCCC")
              (make-run "A" 10 (make-run "G" 1 (make-run "C" 5 (make-end)))))
(check-expect (generate-encoding "")
              (make-end))
Hint: Design a helper function to generate the subproblem "GCCCCC" from the problem "AAAAAAAAAAGCCCCC". Use substring.

Exercise 8. Design a function encode-dna-tree that takes a DNATree as input and produces the run-length encoding. Here are two examples:
(check-expect (encode-dna-tree
               (make-run "A" 10 (make-run "G" 1 (make-run "C" 5 (make-end)))))
              "A10G1C5")
(check-expect (encode-dna-tree (make-end))
              "")
Hint: Follow the template for processing a DNATree. Use number->string.

Exercise 9. Combine generate-encoding and encode-dna-tree to design a function encode that consumes a DNA string and produces its run-length encoding. Again, assume that the given DNA string will only consist of upper-case A, C, G and T. Here are two examples:
(check-expect (encode "AAAAAAAAAAGCCCCC") "A10G1C5")
(check-expect (encode "") "")
Hint: The definition of encode is very short, does not use recursion, and can be written just by looking at the signatures of generate-encoding and encode-dna-tree.

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.

Exercise 10. Design a function generate-decoding that takes a run-length encoding as input and decomposes its decoding problem into a DNATree. Here are two examples:
(check-expect (generate-decoding "A10G1C5")
              (make-run "A" 10 (make-run "G" 1 (make-run "C" 5 (make-end)))))
(check-expect (generate-decoding "")
              (make-end))
Hint: Design a helper function to generate the subproblem "G1C5" from the problem "A10G1C5". Use substring. You may also find the built-in functions string-numeric? and string->number helpful.

Exercise 11. Design a function decode-dna-tree that takes a DNATree as input and produces the DNA string. Here are two examples:
(check-expect (decode-dna-tree
               (make-run "A" 10 (make-run "G" 1 (make-run "C" 5 (make-end)))))
              "AAAAAAAAAAGCCCCC")
(check-expect (decode-dna-tree (make-end))
              "")
Hint: Follow the template for processing a DNATree. Use replicate.

Exercise 12. Combine generate-decoding and decode-dna-tree to design a function decode that consumes the run-length encoding of a DNA string and produces the DNA string. Here are two examples:
(check-expect (decode "A10G1C5") "AAAAAAAAAAGCCCCC")
(check-expect (decode "") "")
Hint: The definition of decode is very short, does not use recursion, and can be written just by looking at the signatures of generate-decoding and decode-dna-tree.