Exercise 4

Submission Details

In this assignment, you will practice writing recursive functions using ordinary recursion (i.e. without accumulators) and iterative recursion (i.e. with accumulators).

VERY VERY IMPORTANT: Unless otherwise stated, you may not use map, filter, foldl, foldr, apply, build-list, and iterated-overlay,underlay,below,beside (those last ones you can use in test-cases for Part 2). You will not receive credit for function definitions using the built in list-iterators..

Exercise 4 Starter Files

Recursion Walkthrough

You can always approach a recursive function in discrete steps:

1. Write the type signature for the function. Example: ; fact: number -> number

2. Write the purpose statement for the function. Example: ; compute the factorial of the given number

3. Determine the base case for your recursion. This is the simplest case, in which the answer is trivial. Example:

; (fact 0) => 1

4. Write a test case (using check-expect) for the base case. Example:(check-expect (fact 0) 1)

5. Write multiple test cases for the recursive case. Remember to test for all edge cases or situations where your function might break. Example:

; using ISL+'s * function to avoid having to do math
(check-expect (fact 1) 1)
(check-expect (fact 5)
                 (* 5 4 3 2 1)) ; luckily it's variadic

6. Finally, write the code itself. Remember that although the specifics will vary, you generally want to have a pattern like this:

(if BaseCase?      ; (= n 0)
    BaseCaseResult ; 1
    RecursiveStep) ; (* n (fact (- n 1)))

6a. If you have multiple cases, remember that the RecursiveStep can be any ISL+ expression, including another if expression. Note that the RecursiveStep often takes the form:

(Combiner FirstPartOfData
         (RecursiveCall RestOfData))

Part 0. Fixing Bugs

In this section, we’ll give you some recursive function that have an error in them (just like on our Quizzes). Your job is to fix each function (the fix should be short, just like in the quizzes – you only need to change at most one line of code).

Activity 1

; sum-of-squares-up-to : number -> number
; This function takes a non-negative integer as input and computes the sum of squares up to that integer.

The function sum-of-squares-up-to should take a non-negative integer n and compute 1^2 + 2^2 + ⋯ + n^2. However, the provided code always runs out of memory (i.e. the recursion never stops). Fix the problem with the function and uncomment the provided check-expect

Activity 2

; multiply-everything : (listof number) -> number
; Computes the product of all numbers in a given list of numbers

The function multiply-everything should take a list of numbers and compute their product. However, the provided code always outputs 0. Fix the problem! (Note that the product of NOTHING is defined to be 1!)

Activity 3

; any-zeros? : (listof number) -> boolean
; A predicate that tests to see if there are any 0s in a given list of numbers

The function any-zeros? should take a list of numbers and output #true if there is any zero in the list or #false otherwise. For example, (any-zeros? empty) should output #false.

First, define test-input-for-any-zeros? to be a (listof number) that reveals the bug in any-zeros?
THEN, fix the problem with the function definition.

Activity 4

Consider the following compound type:

;; A stamp-collection-entry is a struct:
;   (make-stamp-collection-entry String Number Number)
(define-struct stamp-collection-entry (name value count))
;; - `name` is the name of the stamp. It must store a string.
;; - `value` is the monetary value of the stamp. It must store a positive number.
;; -`count` is how many of that stamp you have. It must store a non-negative integer.

The stamp-collection-entry type represents a name of stamp, and a count of how many stamps that have the same value (in dollars). For example, the object (make-stamp-collection-entry "Inverted Jenny" 1000 3) represents a stamp in my collection with the name “Inverted Jenny”, of which I have 3, each of which is worth $1000.

Now, given a list of stamp-collection-entry objects, we’ve given you a broken function total-value that is supposed to compute the total value of a given collection.

; total-value : (listof stamp-collection-entry) -> number
; Computes the total value of a given stamp collection

For example, the below should return 21510 since that’s the result of: 20000(1) + 1000(0) + 500(3) + 1(10)

(total-value
  (list (make-stamp-collection-entry "Inverted Jenny" 20000 1)
        (make-stamp-collection-entry "GWash Z-Grill Stamp" 1000 0)
        (make-stamp-collection-entry "Tyrian Plum" 500 3)
        (make-stamp-collection-entry "Forever Stamps" 1 10)))

Your job is to fix the function’s definition so that the given check-expect passes.

Part 1. Ordinary Recursion

For this section, use ordinary recursion (without an accumulator) for all your functions. This is the simplest form of recursion, and the first version we introduced in the recordings (Lecture 11).

Activity 1. `concat-words`

; concat-words : (listof string) -> string
; Takes a list of words and concatenates them using a comma.

Define a function concat-words that takes a list of strings and concatenates them using a comma (,). A sample function call and output is below:

> (concat-words (list "recursion" "is" "so" "cool"))
"recursion,is,so,cool,"

Hints!

Need help with string functions? Checkout the Quiz Glossary!

Activity 2. `my-iterated-overlay`

Time for everyone’s favorite sequel: “Iterated Overlay Strikes Back.”

Write a recursive function, my-iterated-overlay, that behaves exactly the same way as iterated-overlay. If you’ve forgotten how iterated-overlay works, look it up in the documentation.

; my-iterated-overlay : (number -> image) number -> image
; takes a picture making function (generator) and a number of times to iterate to generate an image

Hints

You will need to return a blank image if the number of iterations is zero. You can do this by returning empty-image (no parentheses needed – it’s a constant, not a function) and on our glossary!
Remember that calling (iterated-overlay func 5) calls func with the sequence 0,1,2,3,4. More generally, calling (iterated-overlay func count) will generate the sequence 0,1,...,n - 1.
Remember that (overlay a b) puts a on top of b, and (overlay b a) puts b on top of a. You need to make sure the iterations stack appropriately. For instance, if gen is an image generator function, the result of calling (my-iterated-overlay gen 5) should place (gen 0) on top, then (gen 1), and so on, with (gen 4) at the bottom.

Calling your function like this:

(my-iterated-overlay (lambda (n)
                       (square (* n 50)
                               "solid"
                               ; make each iteration
                               ; progressively lighter
                               (color (* n 50)
                                      0 
                                      0)))
                     5)   ; number of iterations

should return a result like this:

my-iterated-overlay example output

Note: DON'T COPY AND PASTE THIS IMAGE AS A TEST. Instead, generate the image using iterated-overlay and compare it directly to your my-iterated-overlay.

Activity 3. `my-iterated-any`

Now write a recursive function, my-iterated-any, that takes an arbitrary combiner (a function with the signature: image image -> image like beside, below, overlay, etc.), a generator (picture making function like we normally do), and finally a number of iterations, and combines the results using the specified combiner.

; my-iterated-any: (image image -> image)  (number -> image) number -> image
;                  ~~~~~~~~~~~~~~~~~~~~~   ~~~~~~~~~~~~~~~~  ~~~~~~
;                     <a-combiner-func>      <a-generator>     <a-count>

You can test your function against your implementation of my-iterated-overlay from the previous question. Just like when we moved from count-odd? to count in the tutorial, very little will change between your two functions.

Reminder!

Recall that iterated-overlay, iterated-beside, iterated-above, etc. all perform the same general task: they call a generator some number of times and then combine the resulting images into a single return value. The name of each function specifies the combiner used:

; square-gen : number -> image
(define (square-gen n)
  (square (* n 10)
          "solid"
          (color (* n 50)
                 0 0)))
(check-expect (iterated-beside square-gen 3)
              ; Equivalent to using `beside` to combine
              ; all of the iteration results
              (beside (square-gen 0)
                      (square-gen 1)
                      (square-gen 2)))

Namely, passing in overlay as our combiner:

(my-iterated-any overlay a-generator a-count)

should be equivalent to just calling my-iterated-overlay:

(my-iterated-overlay a-generator a-count)

which, in turn, should be equivalent to calling the original:

(iterated-overlay a-generator a-count)

The same holds for iterated-beside, iterated-above, etc. So for instance, the following should work after your function is defined:

(check-expect (my-iterated-any beside square-gen 3)
              (iterated-beside square-gen 3))

Part 2. Iterative Recursion

To wrap up the assignment, you’ll tweak a few of your functions from Part 1 to use iterative recursion. Recall that iterative recursion differs from ordinary recursion by the use of an accumulator argument which represents the partial result at that current point in time.

Activity 1. `concat-words/iter`

Re-implement concat-words from Part 1 using iterative recursion. The starter code already provides the following main function that initiates the iteration:

; concat-words/iter : (listof string) -> string
; takes a list of strings and concatenates them using iterative recursion

(define (concat-words/iter lst-strs)
  (concat-words-helper lst-strs concat-words-initial-value))

Your job is to define concat-words-initial-value and concat-words-helper. The output should exactly match what the output from your concat-words function given an identical input.

Hint: Initial Value

Define concat-words-initial-value to be the initial value of iterative recursion. What's the equivalent of 0 or (list) for strings? (Spoiler: "", a string with no characters.)

Hint: Helper Function

; concat-words-helper : (listof string) string -> string

Define a function concat-words-helper that actually concatenates the strings using iterative recursion. It should take a list of strings and an accumulator as inputs, and output the concatenated string.

Think carefully about some examples:

What should be the output of (concat-words-helper (list "recursion" "is" "awesome") concat-words-initial-value)?
How about the expression (concat-words-helper (list "is" "awesome") "recursion,")?
What is special about these two examples?

Activity 2. `my-iterated-overlay/iter`

Make a new function that behaves like my-iterated-overlay but uses iterative recursion: my-iterated-overlay/iter. Once again, this function should behave identically to my-iterated-overlay and have the same signature, but must use a helper function with an accumulator.

; my-iterated-overlay/iter : (number -> image), number -> image

Activity 3. `my-iterated-any/iter`

Same deal here. Make a new function that behaves like my-iterated-any but uses iterative recursion.

; my-iterated-any/iter:
; (image image -> image) (number -> image) number -> image
; ~~~~~~~~~~~~~~~~~~~~~~  ~~~~~~~~~~~~~~~  ~~~~~
; <a-combiner>           <a-generator>     <the-count>

Double Checking your Work

Make sure you’ve followed the process outlined in the introduction for every function, and that you’ve thoroughly tested your functions for all possible edge cases.

Double check that you are not using map, filter, foldl, foldr, build-list, apply, or the original iterated-images.rkt file in any of your function definitions (it’s fine to use the image iterators in check-expects).

Before turning your assignment in, run the file one last time to make sure that it runs properly and doesn’t generate any exceptions, and all the tests pass. Make sure you’ve also spent some time writing your OWN check-expect calls to test your code. REMEMBER that the TypeChecker IS NOT a guarantee that your functions work correctly. One of the goals of the class is for you to test your own code.