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

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

*Purposes:*

- Get further practice with numeric recursion, verifying preconditions, and local procedure bindings.
- Think more about efficiency of recursive procedures.
- Explore applications of the Fibonacci numbers in geometric art.

*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 `<grader-151-01@cs.grinnell.edu>`

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

Write and document a procedure, `(`

, that
extracts element `my-list-ref`

`lst`

* n*)

`n`

`>`

`(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: expected a list as first argument, given 3`(my-list-ref 3 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet"))`

`>`

my-list-ref: index too large for list`(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 15)`

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 `fibonacci`

* n*)

`n`

`n`

`n`

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: expected a positive integer, given -5`(fibonacci -5)`

(b) Try evaluating `(`

.
You'll notice that it takes a fairly long time. Why?
`fibonacci`

35)

(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?
`fibonacci`

* n*)

Now write a procedure,
`(`

,
that produces a list of the first `fibonacci-sequence`

* n*)

`n`

`>`

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

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