Numeric Recursion


Due: 11:59 p.m., Tuesday, April 3

Summary: Explore two classic problems that can be solved with numeric recursion.

Purposes:

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.

Submitting: Email your answer to . The title of your email should have the form HW7 and 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.

Preliminaries

Assignment

Problem 1: The Nth Element

Write and document a procedure, (my-list-ref lst n), that extracts element 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)
"indigo"
> (my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 0)
"red"
> (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).

Problem 2: Fibonacci Numbers

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, (fibonacci n), That computes the nth Fibonacci number. Use the basic recursion strategy. Note that there are multiple base cases: There is one base case when n=1, and another when n=2.

Check preconditions using the husk-and-kernel strategy. Use letrec or named let to “hide” the kernel.

For example:

> (fibonacci 1)
1
> (fibonacci 2)
1
> (fibonacci 3)
2
> (fibonacci 4)
3
> (fibonacci 5)
5
> (fibonacci 6)
8
> (fibonacci 7)
13
> (fibonacci -5)
fibonacci: expected a positive integer, given -5

(b) Try evaluating (fibonacci 35). You'll notice that it takes a fairly long time. Why?

(c) Now write a more efficient version of (fibonacci n) 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?

Problem 3: The Fibonacci Sequence

Now write a procedure, (fibonacci-sequence n), that produces a list of the first n Fibonacci numbers. For example:

> (fibonacci-sequence 2)
(1 1)
> (fibonacci-sequence 5)
(1 1 2 3 5)
> (fibonacci-sequence 8)
(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.

Problem 4: Geometric Art with the Fibonacci Numbers

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

Important Evaluation Criteria

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 (davisjan@cs.grinnell.edu)