HW 12: Numeric recursion (CSC 151-01, 2007F)

Calls to
kernel

Summary: In this assignment, you'll consider the structure, preconditions, postconditions, and efficiency of some procedures using numeric recursion.

Purposes: Practice further with numeric recursion, documentation, testing, and analysis. See some forms of numeric recursion that differ from those in the reading and lab.

Collaboration: I encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Warning: So that this assignment is a learning experience for everyone, I may spend class time publicly critiquing your work.

Assignment

Problem 1: How Many Digits?

Here is the definition of a procedure that computes the number of digits in the decimal representation of number:

(define number-of-decimal-digits
  (lambda (number)
    (if (< number 10)
        1
        (+ (number-of-decimal-digits (quotient number 10)) 1))))

b. Add a comment describing the way in which a simpler instance of the problem is created for the recursive call. That is, explain what problem is solved recursively and why you know that that problem is simpler.

c. Document number-of-decimal-digits. In particular, what preconditions does this procedure impose on its parameter?

d. Write a test suite for this procedure (using begin-tests!, test!, and end-tests!).

e. You'll notice that number-of-decimal-digits does not verify its preconditions. Rewrite this procedure so that it has a recursive kernel and a husk that verifies the preconditions. To test your precondition-checking, add tests using test-error! to your test suite.

Problem 2: I have the powers!

Here is the definition of a procedure that computes all the powers of 2 up to 500:

(define powers-of-2-up-to-500
  (lambda ()
    (powers-of-2-up-to-500-kernel 1)))
(define powers-of-2-up-to-500-kernel
  (lambda (power)
    (if (> power 500)
        null
        (cons power (powers-of-2-up-to-500-kernel (* 2 power))))))

a. Generalize this procedure as follows. Write a new procedure, (powers-of-k-up-to-n k n), that builds a list containing all of the powers of k that are less than n. Here are some examples of running this procedure:

> (powers-of-k-up-to-n 2 500)
(1 2 4 8 16 32 64 128 256)
> (powers-of-k-up-to-n 3 100)
(1 3 9 27 81)
> (powers-of-k-up-to-n 10 999999)
(1 10 100 1000 10000 100000)

b. Document this procedure. Think carefully about the preconditions and postconditions.

c. Change define to define$ so you can analyze this procedure. (Be sure to add the $ to both powers-of-k-up-to-n and powers-of-k-up-to-n-kernel.)

Run (analyze (powers-of-k-up-to-n 2 2) powers-of-k-up-to-n-kernel). Then fill out the following table for the specified values of n and k.

Finally, write a formula predicting the number of calls to powers-of-k-up-to-n-kernel for any value of n and k. Explain to the best of your ability why this formula holds.

Important Evaluation Criteria

I will look primarily at the correctness of your code, your analysis, and your documentation.

Submitting Your Homework

Please submit this work via email. The email should be titled CSC151 HW12 and should contain your answers to all parts of this assignment.

Extra credit: Drawing with Powers

For extra credit, make an interesting drawing using the powers-of-k-up-to-n procedure and any drawing techniques you've learned in this class so far (e.,g., spots, region.compute-pixels!, and so forth). Submit your code in the body of an email titled CSC151 HW12 Extra, and attach the image that you created.