<html> <style type=“text/css”> .comment { font-style: italic; color: #c0342d; } .name, .variable, code var, pre var { color: #9e5cb1; } .name { font-weight: bold; } .variable, pre var, code var { font-style: italic; } .keyword { color: #abafb3; } .builtin, .string { color: #417fb8; } .constant { color: #e89f27; } code.pyret { color: black; } table { margin: 1em auto; } table th, table td { padding: 1pt 4pt; } div.dw-content a { text-decoration: underline; } div.dw-content p, div.dw-content li, div.dw-content li p { font-size: 13pt; margin-bottom: 1em; max-width: 750px; } p code, li code { font-size: 11pt; } blockquote { font-size: inherit; } pre kbd, code kbd { background: inherit; color: inherit; box-shadow: none; padding: 0; font: inherit; font-weight: bold; } a.secret { color: inherit; text-decoration: none !important; } a.secret:hover { text-decoration: underline !important; } ol li div.task p:first-child {
margin: 0;
} div.task, p.task {
background-color: #f2d4d7 !important; border: 1px solid #6366a !important; padding: 1em 2.25em; margin: 2em 1.5em;
} p.task, div.task p:first-child {
text-indent: -1.5em;
}
blockquote {
border: 0; margin: 1.5rem;
} </style>
<h1 id=“lab-6-recursion-again-and-again”>Lab 6: Recursion Again and Again</h1> <p>14 October 2022</p>
<h2 id=“learning-objective”>Learning objective</h2>
<p>In class, we’ve been writing <em>recursive</em> functions, where a function body calls the same function, just on a smaller part of the data. This lab gives you practice reading, understanding, and writing functions involving lists and recursion.</p>
<hr style=“margin-top: 3em” /> <p>This lab can be completed in pairs!</p> <p>If you choose to work in a pair, you’ll make a single code file which you’ll upload to Gradescope with both your names.</p> <hr style=“margin-bottom: 3em” />
<h2 id=“exercise-1-tracing-recursion”>Exercise 1: Tracing recursion</h2>
<p>Consider the following recursive function:</p> <pre class=“pyret”>
<span class="keyword">fun</span> <span class="name">product</span>(lst :: List<Number>) -> Number:
<span class="keyword">doc</span>: <span class="string">"Return the product of the numbers in list lst"</span>
<span class="keyword">cases</span> (List) lst:
| empty => 1
| link(f, r) => f * product(r)
<span class="keyword">end</span>
<span class="keyword">where</span>:
product([<span class="keyword">list</span>: 5, 2, 3]) <span class="keyword">is</span> 30
product([<span class="keyword">list</span>: 2, 3]) <span class="keyword">is</span> ...
product([<span class="keyword">list</span>: 3]) <span class="keyword">is</span> ...
product([<span class="keyword">list</span>: ]) <span class="keyword">is</span> ...
end
</pre> <p>In class, you’ve seen this function or ones that are very similar, e.g.,
my-sum
.</p>
<div class=“task”> <p><strong>Task</strong>: Trace the execution of the example</p>
<pre class=“pyret”>
product([<span class="keyword">list</span>: 5, 2, 3])
</pre> <p>showing the values of
f
and
r
and the return value each time the function is called.</p> </div>
<p>Write your solutions as comments in your file in this format:</p> <pre class=“pyret”>
#|
product([list: 5, 2, 3]):
f is 5
r is [list: 2, 3]
return value is 30
it calls product(...)
f is ...
r is ...
return value is ...
it calls product(...)
f is ...
r is ...
return value is ...
it calls product(empty)
return value is ...
|#
</pre>
<h2 id=“exercise-2-sum-of-cubes”>Exercise 2:
sum-of-cubes
</h2>
<p>Consider this template for a function:</p>
<pre class=“pyret”>
<span class="keyword">fun</span> <span class="name">sum-of-cubes</span>(lst :: List<Number>) -> Number:
<span class="keyword">doc</span>: <span class="string">"Return the sum of the cube of each number in the list"</span>
<span class="keyword">cases</span> (List) lst:
| empty => ...
| link(f, r) => ...
<span class="keyword">end</span>
<span class="keyword">where</span>:
sum-of-cubes([<span class="keyword">list</span>: 1, 2, 3]) <span class="keyword">is</span> 36 <span class="keyword">because</span> ...
sum-of-cubes([<span class="keyword">list</span>: 2, 3]) <span class="keyword">is</span> 35 <span class="keyword">because</span> ...
sum-of-cubes([<span class="keyword">list</span>: 3]) <span class="keyword">is</span> 27 <span class="keyword">because</span> ...
sum-of-cubes([<span class="keyword">list</span>: ]) <span class="keyword">is</span> 0
<span class="keyword">end</span>
</pre>
<p>The examples give the right answers but don’t show <em>why</em> we get that answer. That’s what
because
lets us fill in. For example, for
product
in Exercise 1, we could have written:</p>
<pre>
product([<span class="keyword">list</span>: 5, 2, 3]) <span class="keyword">is</span> 30 <span class="keyword">because</span> 5 * product([<span class="keyword">list</span>: 2, 3])
</pre>
<p>An example like this shows how the solution is defined using the solution to a smaller problem. This makes writing the body of the function easy!</p>
<p class=“task”><strong>Task</strong>: Copy the template for
sum-of-cubes
and fill in the
...
in each example with an appropriate expression showing how we get the right answer.</p>
<p>Now you’re ready to fill in the body of the function:</p>
<p class=“task”><strong>Task</strong>: Replace
...
with the appropriate code for both the base case and the recursive case.</p>
<h2 id=“exercise-3-max-pos-num”>Exercise 3:
max-pos-num
</h2>
<p class=“task”><strong>Task</strong>: Fill in the missing parts below to write a function
max-pos-num
that takes in a list of positive numbers and returns the largest number on the list.</p>
<pre class=“pyret”>
<span class="keyword">fun</span> <span class="name">max-pos-num</span>(lst :: List<Number>) -> Number: <span class="keyword">doc</span>: <span class="string">"Return the maximum element of a list of positive numbers; if the list is empty, return -1. Assume that the input list does not have any negative numbers"</span> ... <span class="keyword">where</span>: max-pos-num([<span class="keyword">list</span>: ]) <span class="keyword">is</span> -1 max-pos-num([<span class="keyword">list</span>: 3, 5, 1, 4]) <span class="keyword">is</span> 5 <span class="keyword">end</span>
</pre>
<p>If the list is empty,
max-pos-num
should return
-1
. (Note that every positive number is greater than
-1
!)</p>
<p>Your function should call
num-max
to find the maximum of two numbers.</p>
<h2 id=“exercise-4-bar-chart”>Exercise 4:
bar-chart
</h2>
<p class=“task”><strong>Task</strong>: Fill in the missing parts below to write a function that takes in a list of (non-negative) numbers and draws a bar chart using the given heights.</p>
<pre class=“pyret”>
<span class="keyword">fun</span> <span class="name">bar-chart</span>(lst :: List<Number>) -> Image: <span class="keyword">doc</span>: <span class="string">"Return an image of bars of the given heights next to each other"</span> ... <span class="keyword">end</span>
</pre>
<p>You don’t need to write test cases for this function, but you should call it to make sure it works as intended. For example,</p>
<pre class=“pyret”>
bar-chart([<span class="keyword">list</span>: 100, 200, 50, 75, 100, 10])
</pre>
<p>might look like this:</p>
<p><img src=“https://www.cs.vassar.edu/~cs101/images/bar-chart.png” style=“max-width: 50%; max-height: 200px” /></p>
<p>But you can feel free to adjust the appearance.</p>
<p><strong>Hint</strong>: You may want to refer to the <a href=“https://www.pyret.org/docs/latest/image.html”>Pyret image documentation</a> – and note the existence of <a href=“https://www.pyret.org/docs/latest/image.html#%28part._image_empty-image%29”>
empty-image
</a>!</p>
<h2 id=“exercise-5-long-strings”>Exercise 5:
long-strings
</h2>
<p class=“task”><strong>Task</strong>: Fill in the missing parts below 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
.</p>
<pre class=“pyret”>
<span class="keyword">fun</span> <span class="name">long-strings</span>(lst :: List<String>, len :: Number) -> List<String>:
<span class="keyword">doc</span>: <span class="string">"Return a list consisting of those elements of lst that are longer than len"</span>
<span class="keyword">cases</span> (List) lst:
| empty => ...
| link(f, r) =>
<span class="keyword">if</span> string-length(f) > len:
...
<span class="keyword">else</span>:
...
<span class="keyword">end</span>
<span class="keyword">end</span>
<span class="keyword">where</span>:
long-strings([<span class="keyword">list</span>: ], 0) <span class="keyword">is</span> empty
long-strings([<span class="keyword">list</span>: <span class="string">"the"</span>, <span class="string">"quick"</span>, <span class="string">"brown"</span>, <span class="string">"fox"</span>], 5)
<span class="keyword">is</span> empty
long-strings([<span class="keyword">list</span>: <span class="string">"the"</span>, <span class="string">"quick"</span>, <span class="string">"brown"</span>, <span class="string">"fox"</span>], 4)
<span class="keyword">is</span> [<span class="keyword">list</span>: <span class="string">"quick"</span>, <span class="string">"brown"</span>]
long-strings([<span class="keyword">list</span>: <span class="string">"the"</span>, <span class="string">"quick"</span>, <span class="string">"brown"</span>, <span class="string">"fox"</span>], 2)
<span class="keyword">is</span> [<span class="keyword">list</span>: <span class="string">"the"</span>, <span class="string">"quick"</span>, <span class="string">"brown"</span>, <span class="string">"fox"</span>]
<span class="keyword">end</span>
</pre>
<p><strong>Optional</strong>: After you have completed the code for
long-strings
, show how to use
filter
to accomplish the same thing that
long-strings
does but with less code.</p>
<h2 id=“submitting-the-lab”>Submitting the lab</h2>
<ul> <li><p>When you’ve completed the exercises, show your code to your instructor or one of the coaches.</p></li> <li><p>Then upload your
lab06.arr
file to the Lab 6 assignment on <a href=“https://www.gradescope.com”>Gradescope</a>.</p></li> </ul> </html>