# Lab 6: Recursion Again and Again

15 October 2021

## Learning Objectives

The purpose of this lab is to give you practice reading, understanding, and writing functions involving lists and recursion.

# Setup

Create the file `lab06.arr`

and copy/paste the following into it:
`import lists as L`

As usual, ask your instructor or a coach if you're stuck. Remember to save your work every so often.

# Exercise 1: Tracing

Look at the following recursive function. In class, you've seen this function or ones that are very similar (e.g., `my-sum`

).

fun my-product(lst :: List<Number>) -> Number: doc: ```returns the product of the numbers in list lst``` cases (List) lst: | empty => 1 | link(f, r) => f * my-product(r) end where: my-product(empty) is ... my-product([list: 2, 3]) is ... my-product([list: 5, 2, 3]) is ... end

Trace the execution of the `my-product([list: 5, 2, 3])`

, showing the values of `lst`

, `f`

, and `r`

and the return value each time the function is called.
If `lst`

is `empty`

, there are no values for `f`

and `r`

, so you can leave those lines out. You should fill in the return values (in reverse order)
after you've shown the values of `lst`

, `f`

, and `r`

for each call.

Write your solutions as comments in your file in this format:

#| my-product([list: 5, 2, 3]): lst is [list: 5, 2, 3] f is ... r is ... return value is ... it calls my-product(...) f is ... r is ... return value is ... it calls ... it calls my-product(empty) return value is ... |#

# Exercise 2: sum-of-cubes

Fill in the missing parts to write a function that takes in a list of Numbers and returns the sum of the cubes of the numbers:

fun sum-of-cubes(lst :: List<Number>) -> Number: cases (List) lst: | empty => ... | link(f, r) => ... end where: sum-of-cubes(empty) is 0 sum-of-cubes([list: 1, 2, 3]) is 36 end

# Exercise 3: list-to-string

Fill in the missing parts to write a function that takes in a list of Strings and returns a single string with all the strings “glued” together.
For example `list-to-string([list: "ab", "cd"])`

should return the string `"abcd"`

. Your function should call `string-append`

to glue two strings together.

fun list-to-string(lst :: List<String>) -> String: doc: ```returns a single string consisting of all of the strings in list lst 'glued' together``` ... where: list-to-string(empty) is "" list-to-string([list: "hello"]) is "hello" list-to-string([list: "hello ", "world"]) is "hello world" list-to-string([list: "one", "two", "three"]) is "onetwothree" end

# Exercise 4: max-pos-num

Fill in the missing parts to write a function `max-pos-num`

that takes in a list of positive numbers and
returns the largest number on the list. If the list is empty, `max-pos-num`

should return -1. Note that
every positive number is greater than -1. Your function should call `num-max`

to find the maximum of two
numbers.

fun max-pos-num(lst :: List<Number>) -> Number: doc: ```returns the maximum element of a list of positive numbers; if the list is empty, returns -1. Assume that the input list does not have any negative numbers``` ... where: max-pos-num(empty) is -1 max-pos-num([list: 3, 5, 1, 4]) is 5 end

# Exercise 5: long-strings

Fill in the missing parts to write a function `long-strings`

that takes in a list of strings `lst`

and a Number `len`

and returns a list that includes all of the strings
from `lst`

whose length is greater than `len`

.

fun long-strings(lst :: List<String>, len :: Number) -> List<String>: doc: ```returns a list consisting of those elements of lst that are longer than len``` cases (List) lst: | empty => ... | link(f, r) => if string-length(f) > len: ... else: ... end end where: long-strings(empty, 0) is empty long-strings([list: "the", "quick", "brown", "fox"], 4) is [list: "quick", "brown"] long-strings([list: "the", "quick", "brown", "fox"], 5) is empty long-strings([list: "the", "quick", "brown", "fox"], 2) is [list: "the", "quick", "brown", "fox"] end

**Optional**:
After you have completed the code for `long-strings`

,
show how to use `L.filter`

to accomplish the same thing that `long-strings`

does (with much less code).

## Submitting the Lab

- When you've complete the exercises, show your code to me or one of our coaches.

- Upload your
`lab06.arr`

file to the Lab 6 assignment on Gradescope.