Simply Scheme Chapter 11 – Introduction to Recursion

My notes on this chapter are short because I found it very easy, which I expected. I’ve looked basic recursion stuff before in detail, so this is more of a review.

This chapter introduces the “combining” method of recursion with an example of a procedure that does the following:

The basic thing they do is work their way up, first start with a procedure that can handle the one letter case, then the two letter case, then the three letter case, and then starting to look for patterns.

Every recursive procedure has the following attributes:
1. a recursive case where the procedure calls itself, and
2. a base case that the procedure can address without calling itself
3. each recursive call gets us closer to the base case

for the solution for downup:

the recursive case is when the count = 1, in which case downup returns the wd. The recursive case is when count > 1, in which case downup makes a recursive call to itself while also returning wd on either side of the recursive call. And the recursive case gets closer to the base case due to the bl wd, which reduces the length of wd by 1.

Boring Exercises

✅ Exercise 11.1

Write downup4 using only the word and sentence primitive procedures.

I did some extra analysis and testing beyond what the exercise required.

The domain of this procedure is words (including numbers) or sentences. The range is a sentence with the characters from a word displayed in the “downup” fashion, or a sentence with words being “downup”‘ed like the characters of a word. This will be clearer with examples.

downup4 works correctly with a 4-letter word, which is the intended case:

It does not work correctly with 3 letter words. Note the unnecessary instances of 'h

It also does not work correctly with 5 letter words. Note the jump from 3-character cak to one-character c:

If you use downup4 on a sentence, the words are treated like the individual characters in the previous examples:

so it goes down from potato ninja tomato hat to potato ninja tomato to potato ninja to potato and then back up.

✅ Exercise 11.2

When you teach a class, people will get distracted if you say “um” too many times. Write a count-ums that counts the number of times “um” appears in a sentence:

Here are some special-case count-ums procedures for sentences of particular lengths:

Write count-ums recursively.

Note: this was my non-recursive solution for this problem back in chapter 8:

I think a solution has to handle the following things:
1. Seeing if the sentence is empty (the base case)
2. Seeing if a particular word is an um
3. Adding 1 if a word is an um
4. Not adding 1 if a word is not an um
5. Recursively calling count-ums with a shorter version of the sentence regardless of whether the word is an um or not

So based on the examples in the book this was my first attempt at trying to meet these criteria:

it works on test cases. I do wonder if there might be a more elegant way to organize it though. Seems okay though. Here’s a tree:

After a while I thought of a version with a helper procedure:

I like this version better, since it avoids nesting an if in the main part of the program.

✅ Exercise 11.3

Write a procedure phone-unspell that takes a spelled version of a phone number, such as POPCORN, and returns the real phone number, in this case 7672676. You will need a helper procedure that translates a single letter into a digit:

Here are some some special-case phone-unspell procedures:

Write phone-unspell recursively.

I changed their helper procedure so that it could handle capital letters:

and here is my solution:

Test:

Real Exercises

🤔Exercise 11.4

Who first said “use what you have to get what you need”?

Legit could not figure out the answer to this one despite heavy googling.

UPDATE: A commenter below says the answer is General Giap and links this
Mystery solved!

✅ Exercise 11.5

Write a procedure initials that takes a sentence as its argument and returns a sentence of the first letters in each of the sentence’s words:

Answer:

✅ Exercise 11.6

Write a procedure countdown that works like this:

answer:

I noticed that AnneB thought to handle the case where the number used is not a positive integer, so I wrote my own way to address that before reading hers:

✅ Exercise 11.7

Write a procedure copies that takes a number and a word as arguments and returns a sentence containing that many copies of the given word:

answer:

After adding the check for valid numbers in the last exercise, I realized maybe I should do the same here:

Results: