Due: 11:59 p.m., Tuesday, April 3
Summary: Explore two classic problems that can be solved with numeric recursion.
Collaboration: We encourage you to work in groups of size two. You may, however, work alone or work in a group of size three. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Email your answer to
<firstname.lastname@example.org>. The title of your email
should have the form
should contain your answers to all parts of the assignment. Scheme code
should be in the body of the message.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
Write and document a procedure,
n of a list.
Your procedure should verify its preconditions and give helpful error
messages. For example,
(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 5)
(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 0)
(my-list-ref 3 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet"))my-list-ref: expected a list as first argument, given 3
(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 15)my-list-ref: index too large for list
Even though this procedure does the same thing as
list-ref, you should not use
list-ref to implement it. Instead, your goal
is to figure out how
list-ref works, which means
that you will need to implement this procedure using recursion.
Hint: When recurring, you will need to simplify both the numeric parameter (probably by subtracting 1) and the list parameter (probably by taking its cdr).
The Fibonacci numbers can be defined as follows:
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)
(a) Write a procedure,
That computes the
nth Fibonacci number.
Use the basic recursion strategy. Note that there are multiple base
cases: There is one base case when
and another when
Check preconditions using the husk-and-kernel strategy.
letrec or named
let to “hide”
(fibonacci -5)fibonacci: expected a positive integer, given -5
(b) Try evaluating
You'll notice that it takes a fairly long time. Why?
(c) Now write a more efficient version of
using the helper recursion strategy. Take some time to reflect on what
additional parameters your helper procedure should have. What can extra
parameters can you use to avoid repeated computations?
Now write a procedure,
that produces a list of the first
numbers. For example:
(1 1 2 3 5)
(1 1 2 3 5 8 13 21)
Your first goal should be correctness. Then, strive to make your algorithm as concise and/or efficient as possible.
(a) Write a procedure to create some form of geometric art that is somehow based on the Fibonacci numbers. Consider the roles of size, position, shape, and color.
Please document your procedure with the 6 Ps so we will know how to use your procedure. If your procedure takes longer than two minutes to run, please attach two sample images to your email.
(b) Write a brief (1 paragraph) statement explaining your design intentions for your geometric art procedure. If you discuss color, use appropriate terminology.
Your work will be judged based on its correctness, efficiency, and concision. Your solution to the last problem will also be judged on its clarity and creativity.
Janet Davis (email@example.com)