# ARCHIVED: ~~Lab 6: Understanding Recursion~~ :::danger ## This is the S26 version of this document. Refer to the [course webpage](https://brown-csci0111.github.io/pages/home.html) for the up-to-date version. ::: In lecture, we have started to write *recursive* functions, where a function body calls the same function to process a smaller part of the data. This lab gives you practice with understanding how this works and writing recursive functions of your own. In the first part of lab, you'll draw function diagrams on paper to visualize recursive function calls. In the second half, we'll practice writing some recursive programs. Call a TA over if you get confused or need clarification.  [Source](https://www.freepik.com/free-vector/hand-drawn-baker-cartoon-illustration_61105121.htm) ## Resources [Lab 6 Presentation Slides](https://docs.google.com/presentation/d/1tLMtnYFDBkqHv5Lv-fPao8TjD89oo4usN2HVtuMoap4/edit?usp=sharing) ## Execution diagrams You have seen an example of such a diagram in class and practiced reasoning about it in Drill 15. For a reminder, <details> <summary><strong>Execution diagram for <code>list-sum</code></strong></summary> (Some semesters we call this something like `sum-lst` or `my-sum`)  Each of the boxes gives the *local context* for the corresponding function call (for example, the orange box gives the local context for the function call `list-sum([list: 3, 1])`, which is color-coded in orange). A *local context* is a part of the program directory created to keep track of the names specific to a function, while the function is running. The vertical placement of the function calls is important, and shows how a function call is *pending* until the lower function calls finish. For example, `list-sum([list: 3, 1])` is pending until `list-sum([list: 1])` and `list-sum(empty)` finish. The arrows on the right side of the diagram show how the first answer we get back is for the empty case, and how having that answer lets Pyret resolve each pending function call in order. </details> ## Part 1: Reasoning about recursive execution ### Exercise 1: Binning Numbers by their Signs In data analysis, we often take a column of data and convert it into a small number of fixed "bins": this lets us cluster data for analysis. For example, we refer to December, January, and February as "winter", while March, April, and May are referred to as "spring". The following function bins numbers based on their signs (positive, negative, and zero): ``` fun nums-to-signs(numlist :: List<Number>) -> List<String>: cases (List) numlist: | empty => empty | link(fst, rst) => sign = if fst > 0: "pos" else if fst == 0: "zero" else: "neg" end # eval point A link(sign, num-to-signs(rst)) end where: nums-to-signs([list: -1, 6, 0]) is [list: "neg", "pos", "zero"] end ``` **Task 1:** On paper, draw an execution diagram for `nums-to-signs([list: -1, 6, 0])`. What function calls are pending at the moment that `nums-to-signs(empty)` is called in your diagram? **Task 2:** When people first see recursion, they often believe that the function will return the answer for the `empty` case (since in the code, the function returns a simple value in that case). What aspects of your diagram illustrate that this doesn't happen? ___ ### *CHECKPOINT:* Call over a TA once you reach this point. ___ ### Exercise 2: Counting Emoticons Impressed by your recursion skills, the engineers of a cow chat service reached out to you asking for your help on some research. They want to study the frequency of emoticons used within their system. The importer has created a function `is-emoticon` that checks whether a text is a valid emoticon. The `count-emoticon` function uses `is-emoticon` to tally up the number of emoticons used in their service. ``` fun is-emoticon(msg :: String) -> Boolean: (msg == ":)") or (msg == "XD") or (msg == ":'(") or (msg == ":P") end fun count-emoticon(msgs :: List<String>) -> Number: cases (List) msgs: | empty => 0 | link(fst, rst) => if is-emoticon(fst): 1 + count-emoticon(rst) else: count-emoticon(rst) end end end ``` Consider the following example: ``` count-emoticon([list: "XD", "LOL", ":P"]) ``` **Task 3:** Draw the execution diagram for the call `count-emoticon([list: "XD", "LOL", ":P"])` **Task 4:** With a pen or highlighter, indicate the calls that are pending at the point `count-emoticon` is called with the empty list. Using a different color, indicate the calls that are pending at the point `is-emoticon` is called with the second element in the list, “LOL” *Hint:* Remember that the pending calls are the ones made on list elements that precede a given element (are higher up on the diagram), so you will have fewer pending calls indicated for this example than the previous one. **Task 5:** Why don't calls to `is-emoticon` appear in your execution diagram? How is it used within `count-emoticon`? Write down your answer. **Task 6:** Compare the first sequence of pending calls from task 5 to the sequence of pending calls for the `nums-to-signs` problem. What do you notice is the same and different between the two sequences of calls? Write down your answer. **Task 7:** For `nums-to-signs` and `count-emoticon`, determine if the function's primary role is to `map` or to `filter` list elements. Identify the characteristics of these functions that differentiate between the two roles. Write down your answer. <!-- **Task 9:** Now, think about whether each of the functions you worked on involved mapping or filtering. What hypothesis can you make about the sequence of "local context" terms for `map`-like functions versus `filter`-like functions? Write down your answer. --> ___ ### *CHECKPOINT:* Call over a TA once you reach this point. ___ ## Part 2: Recursive Programming Practice Imagine that you are playing a game that asks you to generate a collection of words from a specified set of letters. The following functions check various conditions against those words in order to score the game. **Task 8:** Develop a function `all-have-t :: List<String> -> Boolean` that takes a list of words and returns true if **every** word in the list contains the letter `"t"`. **Task 9:** Develop a function `any-have-t :: List<String> -> Boolean` that takes a list of words and returns true if **any** word in the list contains the letter `"t"`. **Task 10:** What differences do you notice between the logic of `all-have-t` and `any-have-t`? **Task 11:** On paper, draw the execution diagram of `any-have-t(["car", "cat", "cab"])` ___ ### *CHECKPOINT:* Call over a TA once you reach this point. ___ Now we want to write some functions to score the game. For each of the following scoring functions that you implement, write sequential where-examples (as seen in class): ``` fun sum(numlist :: List<Number>) -> Number: cases (List) numlist: | empty => 0 | link(fst, rst) => fst + sum(rst) end where: sum([list: 4, 7, 2]) is 4 + sum([list: 7, 2]) sum([list: 7, 2]) is 7 + sum([list: 2]) sum([list: 2]) is 2 + sum([list: ]) sum([list: ]) is 0 end ``` **Task 12:** Develop a function `compute-score1 :: List<String> -> Number` that takes a list of words and produces a score which is the sum of the lengths of all the words. **Task 13:** Develop another scoring function `compute-score2 :: List<String> -> Number` in which the score for a single word is 1 if it has four or fewer characters. For words longer than four characters, its score is the length of the word. **Task 14:** Look at the two functions you've just written. Is there a common pattern to writing "scoring"-style functions? At what point do they differ? **Task 15:** If you aren't sure how these functions are working, draw out an execution diagram for each task to trace out how the computation is evolving. ___ ### *CHECKPOINT:* Call over a TA once you reach this point. ___ ## Part 3: Richer Recursion Practice **Task 16:** Write a function `make-circles(rad-list :: List<Number>) -> Image` that takes in a list of numbers representing radii and produces an image consisting of adjacent green circles. Each circle should have the radius of its corresponding list index. In other words, the first circle should have the same radius as the first element of rad-list, and so on. The final circle in the image should always be a black circle of radius 10, which is not represented in the list. For example, `make-circles([list: 40,60,10])` should produce an image that looks like the following:  **Task 17:** Note: for this task, think about how you would implement this. You will code it in the next task. Now, we want a function that lets us change the colors of the circles as well. The function `make-better-circles(rad-list :: List<Number>, color-list :: List<String>) -> Image` should take in: - A list of Numbers representing radii - A list of Strings representing valid Pyret colors As before, the function should output an image of adjacent circles. This time, each circle should have both the color and radius of its corresponding list index. The first circle should be the same color as the first element of color-list and the size of the first element of rad-list, and so on. The final circle in the image should still be a black circle of radius 10, not in either list. For example, `make-better-circles([list: 30,40,50], [list: "orange", "olive", "blue"])` should produce an image that looks like the following:  Draw out a sequence of related examples to show how the two lists interact within and across the examples. Since this involves images, you can draw the examples out on paper, but you should still be explicit about defining the input lists. **Task 18:** Write the code for this problem. (*Note: Part of the point of this problem is to have you think through which of the two input lists is "driving" generation of the circles. That should be the list you break down in the `cases` expression.)* :::info Having trouble dealing with 2 lists? Apart from using `cases` statements, we can access a list's first and rest field by using `.first` and `.rest`. For example, if a list is named "my-list", we can access the first item in the list by typing `my-list.first`. ::: **Task 19:** Modify your `make-better-circles` function to raise an error if there aren't enough colors in the color list for all of the radii ___ ### *CHECKPOINT:* Call over a TA once you reach this point. ___ **Extra Time Task:** Write a new version of `make-better-circles` called `make-circles-recycle` in which the list of colors can be shorter than the list of radii. The circles should cycle through the list of colors in order, repeating until all circles have been generated. For example, given a list of four radii and the two colors `[list: "red", "brown"]`, the circles would appear in colors red, brown, red, brown. *Warning: it is easy to make this unnecessarily complicated, especially if you have programmed before. This is an exercise in elegance. If you find yourself thinking about this by counting and modulo, for example, try again!* ___ ### *CHECKPOINT:* Call over a TA once you reach this point. ------ ## Theme Song [Let Her Cook by GloRilla](https://open.spotify.com/track/1nF1SpkNfgPPozcXh2hvGU?si=b4642075f77c4c8b) > Brown University CSCI 0111 (Spring 2026) > Have questions? Refer to [Ed](https://edstem.org/us/courses/93677) > Check out our glorious [Spotify](https://open.spotify.com/playlist/0UdtGEq1aamMp78T0Ehxg4) playlist! <iframe data-testid="embed-iframe" style="border-radius:12px" src="https://open.spotify.com/embed/playlist/0UdtGEq1aamMp78T0Ehxg4?utm_source=generator" width="100%" height="352" frameBorder="0" allowfullscreen="" allow="autoplay; clipboard-write; encrypted-media; fullscreen; picture-in-picture" loading="lazy"></iframe> > **Feedback form** <iframe src="https://docs.google.com/forms/d/e/1FAIpQLSdjTJkyCYkLXcnYfzkugwD8FDuJQZwM5SAER4pwvU_QxTuRSw/viewform?embedded=true" width="640" height="977" frameborder="0" marginheight="0" marginwidth="0">Loading…</iframe>