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 complex-recursion.scm.
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.
A string is called a palindrome if reversing the characters of the
string results in the same string. A few examples of palindromes are
"radar", "civic", and "aabaa". Document and write a procedure
(palindrome? str) that checks to see if the string str
is a palindrome. You may not use any string comparison procedures
for this problem (e.g. string=?, string<=?, etc.) nor may you build
other strings along the way. You must leave the string as a string.
You may not, for example, turn it into a list of characters. You will
find string-ref, string-length, and char=? useful procedures for
solving this problem.
> (palindrome? "hello")
#f
> (palindrome? "civic")
#t
Hint: Use numeric recursion with the position of the character.
caddadadr proceduresAs we’ve seen, Scheme has some useful procedures like caddr and cdadr that allow us to quickly access values in pair structures.
However, these short-hand procedures are only available for up to four pair accessor operations.
For this problem, you should write and document a recursive procedure (make-pair-accessor name) that produces a pair accessor procedure from a string of its Scheme-style name.
Consider the following example inputs:
> (define my-cadr (make-pair-accessor "cadr"))
> (my-cadr (list 1 2 3))
2
> (define my-cdaddr (make-pair-accessor "cdaddr"))
> (map iota (iota 5))
'(() (0) (0 1) (0 1 2) (0 1 2 3))
> (my-cdaddr (map iota (iota 5)))
'(1)
> (define my-cdddddr (make-pair-accessor "cdddddr"))
> (my-cdddddr (iota 10))
'(5 6 7 8 9)
You may assume that make-pair-accessor will only be called on valid input strings; you do not need to validate the input in your code, but you should include a description of the valid inputs in your preconditions.
Hint: You can use compose to recursively build procedures in a similar way as using cons to recursively build lists. For example, (compose square), returns the procedure square.
Submit complex-recursion.scm to Gradescope.
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.
[] 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. (`string-length` is allowed)
[] All three problems include a wide variety of tests which cover edge cases beyond those presented in the assignment.