We are providing you with starter code, CC7-template.scm. You should download this file and upload the given code to a new .scm file named LASTNAME-complex-reucrsion.scm where you replace LASTNAME with your last name.
You are required to document every procedure that you write using the documentation style of our course. Tests are optional, but likely helpful in determining if your code is working as desired.
At the top of your file, make sure to include your name, and any acknowledgements according to our collaboration policy. Now is a great time to review those collaboration policies.
Write a procedure, (closest-to-zero-a values), that, given a list of real numbers (including both positive and negative numbers) as input, returns the
value closest to zero in the list. Your solution must use basic recursion. Basic recursion refers
to the original version of recursion we learned, not tail recursion.
Hint: Think about how, given two numbers, you determine which is closer to zero.
Note: If there are multiple values equally close to zero, and all are closer than any other value, you may return any of them. You may assume that the list only contains numbers and that the list contains at least one value.
Write a tail-recursive version called closest-to-zero-b that uses a
local helper. Your helper should likely take closest-so-far and
remaining as parameters.
Explain which version of closest-to-zero you prefer and why.
(there is no right answer here, as long as you justify your answer)
We sometimes refer to the two-element-box created by the cons procedure as a “pair.” In practice in Scamper, (cons {??} {??}) and (pair {??} {??}) produce different structures, but pragmatically we think of them as quite similar. It can be very useful to identify just how many “pairs” (created through pair or cons) appear in a structure, in part because it tells us a bit about the effort required to make the structure.
Write and document a procedure, (count-pairs value), that takes as input a Scheme value (e.g., a pair structure or list) and determines how many pairs appear in that structure.
For example,
> (count-pairs null)
0
> (count-pairs 5)
0
> (count-pairs (cons 5 null))
1
> (count-pairs (list 5))
1
> (count-pairs (pair null 5))
1
> (count-pairs (pair (pair "a" "b") "c"))
2
> (count-pairs (list 1 2 3 4 5))
5
> (count-pairs (list null null null))
3
> (count-pairs (list (list 1 2 3) (list 4 5)))
7
As the examples above suggest, you need to look within lists to determine if their individual elements themselves contains pairs. (You may find that this happens automatically as you handle non-lists.)
It is possible to solve this using tail recursion, however the solution is unconventional. Attempt to solve this problem using tail recursion, and describe what makes the solution differ from our usual tail recursion. Alternatively, if you can’t come up with a solution, describe the problem with our usual tail recursion solution and why it doesn’t work here.
Working code is not required for this problem.
Submit your .scm file to Gradescope, using the name according to the top of these instructions.
In grading your submission, we will look for the following at each level. Note that if a criteria does not pass a lower level, we will likely not check for criteria at the higher levels. We may also identify other characteristics that move your work between levels.
You should read through the rubric and verify that your submission meets the rubric.
Submissions that lack any of these characteristics will get an N.
[] Includes the specified file (correctly named).
[] Includes an appropriate header on the file that indicates the course, author, acknowledgements, etc.
[] Acknowledges appropriately.
[] Code runs in scamper.
Submissions that lack any of these characteristics but have all of the prior characteristics will get an R.
[] Code is well-formatted with appropriate names and indentation.
[] Code submission is organized with comments to indicate the start of new problems.
[] All Gradescope tests pass for Problem 1.
[] All Gradescope tests pass for Problem 2.
[] All solutions use recursion as the main technique.
[] Problem 1a uses "regular" recursion, Problem 1b uses tail recursion.
[] Documentation in the 151 style is included for all code, and contains correct information.
Submissions that lack any of these characteristics but have all of the prior characteristics will get an M.
[] All code is exceptionally organized and easy to read, through the use of comments (to explain the purpose of different pieces of the code), decomposition, and highly intuitive naming choices.
[] All solutions do not make calls to built-in recursive procedures such as `filter`, `map`, `append`, `tally-all`, etc.
[] Problems 1a, 1b, and 2a include a wide variety of tests which cover edge cases beyond those presented in the assignment.
[] Thoughtful and correct explanation given in problem 2b.