## 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:

#### ✅ Exercise 11.6

Write a procedure countdown that works like this:

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: