CS61A Summer 2011 Homework 3
Topic: Recursion and Iteration
Reading: Abelson & Sussman, Section 1.2 through 1.2.4 (pages 31-47)
Topic: Recursion and iteration
Reading: Abelson & Sussman, Section 1.2 through 1.2.4 (pages 31–47)
1. Write a procedure squares that takes a sentence of numbers as its argument and returns a sentence of the squares of the numbers - BUT make it generate an iterative process!
> (squares ’(2 3 4 5))
(4 9 16 25)
2. Write multiply that takes a sentence of numbers and multiplies them together - BUT make it generate an iterative process!
>(multiply ‘(2 3 4 5))
3. A “perfect number” is defined as a number equal to the sum of all its factors less than itself. For example, the first perfect number is 6, because its factors are 1, 2, 3, and 6, and 1+2+3=6. The second perfect number is 28, because 1+2+4+7+14=28. What is the third perfect number? Write a procedure (next-perf n) that tests numbers starting with n and continuing with n+1, n+2, etc. until a perfect number is found. Then you can evaluate (next-perf 29) to solve the problem. Hint: you’ll need a sum-of-factors subprocedure.
[Note: If you run this program when the system is heavily loaded, it may take half an hour to compute the answer! Try tracing helper procedures to make sure your program is on track, or start by computing (next-perf 1) and see if you get 6.]
4. Abelson & Sussman, exercise 1.16
5. Give an algebraic formula relating the values of the parameters b, n, counter, and product of the expt and exp-iter procedures given near the top of page 45 of Abelson and Sussman. (The kind of answer we’re looking for is “the sum of b, n, and counter times product is always equal to 37.”) (HINT: you might want to make a chart of values)
6. Explain the effect of interchanging the order in which the base cases in the cc procedure on page 41 of Abelson and Sussman are checked. That is, describe completely the set of arguments for which the original cc procedure would return a different value or behave differently from a cc procedure coded as given below, and explain how the returned values would differ.
(define (cc amount kinds-of-coins)
((or (< amount 0) (= kinds-of-coins 0)) 0)
((= amount 0) 1)
(else ... ) ) ) ; as in the original version
7. (OPTIONAL) The partitions of a positive integer are the different ways to break the integer into pieces. The number 5 has seven partitions:
5 (one piece)
4, 1 (two pieces)
3, 2 (two pieces)
3, 1, 1 (three pieces)
2, 2, 1 (three pieces)
2, 1, 1, 1 (four pieces)
1, 1, 1, 1, 1 (five pieces)
The order of the pieces doesn’t matter, so the partition 2, 3 is the same as the partition
3, 2 and thus isn’t counted twice. 0 has one partition.
Write a procedure number-of-partitions that computes the number of partitions of its nonnegative integer argument. (HINT: This should be VERY similar to count-change)
8. (OPTIONAL) Compare the number-of-partitions procedure with the count-change procedure by completing the following statement:
“Counting partitions is like making change, where the coins are …”
Extras for Experts
1. Abelson & Sussman, exercises 1.35, 1.37, 1.38
(Some of what is hard about the problems is the “math”, not the computer programming)
2. (Much harder!) Now write number-of-partitions to generate an iterative process; every recursive call must be a tail call.
Unix feature of the week: mkdir, cd, pwd, ls
Emacs feature of the week: C-M-f, C-M-b, C-M-n, C-M-p (move around Scheme code)