# Lab 0.3:

## Recursion

In order to understand recursion, one must first understand recursion.

By now you're very familiar with the idea of implementing a function by composing other functions. In effect we are breaking down a large problem into smaller parts. The idea of recursion—as usual, it sounds simpler than it actually is—is that one of the smaller parts can be the same function we are trying to implement.

At clothes stores they have arrangements with three mirrors hinged together. If you keep the side mirrors pointing outward, and you're standing in the right position, what you see is just three separate images of yourself, one face-on and two with profile views. But if you turn the mirrors in toward each other, all of a sudden you see what looks like infinitely many images of yourself. That's because each mirror reflects a scene that includes an image of the mirror itself. This self-reference gives rise to the multiple images.

Recursion is the idea of self-reference applied to computer programs. Here's an example:

```"I'm thinking of a number between 1 and 20."
(Her number is between 1 and 20.  I'll guess the halfway point.) "10."
"Too low."
(Hmm, her number is between 11 and 20.  I'll guess the halfway point.) "15."
"Too high."
(That means her number is between 11 and 14.  I'll guess the halfway point.) "12."
"Got it!"
```

We can write a procedure to do this:

``````(define (game low high)
(let ((guess (average low high)))
(cond ((too-low? guess) (game (+ guess 1) high))
((too-high? guess) (game low (- guess 1)))
(else '(I win!)))))
``````

This isn't a complete program because we haven't written `too-low?` and `too-high?`. But it illustrates the idea of a problem that contains a version of itself as a subproblem: We're asked to find a secret number within a given range. We make a guess, and if it's not the answer, we use that guess to create another problem in which the same secret number is known to be within a smaller range. The self-reference of the problem description is expressed in Scheme by a procedure that invokes itself as a subprocedure.

The idea of self-reference also comes up in some paradoxes: Is the sentence "This sentence is false" true or false? (If it's true, then it must also be false, since it says so; if it's false, then it must also be true, since that's the opposite of what it says.) This idea also appears in the self-referential shapes called fractals that are used to produce realistic-looking waves, clouds, mountains, and coastlines in computer-generated graphics.

## finish this before section; refer back when necessary

There are many ways of understanding recursion. You may not have to do all the reading after things "click". However, Simply Scheme Chapter 14 is very useful and you should refer to it often, especially when stuck on an exercise that involves recursion.

# Exercise 0.

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:

``````(count-ums '(today um we are going to um talk about the combining um method))
3
``````

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

``````(define (count-ums0 sent)
0)

(define (count-ums1 sent)
(if (equal? 'um (first sent))
1
0))

(define (count-ums2 sent)
(if (equal? 'um (first sent))
(+ 1 (count-ums1 (bf sent)))
(count-ums1 (bf sent))))

(define (count-ums3 sent)
(if (equal? 'um (first sent))
(+ 1 (count-ums2 (bf sent)))
(count-ums2 (bf sent))))``````

Write count-ums recursively.

# Exercise 1.

Write a procedure countdown that works like this:

``````(countdown 10)
(10 9 8 7 6 5 4 3 2 1 blastoff!)``````

# Exercise 2.

Write a procedure numbers that takes a sentence as its argument and returns another sentence containing only the numbers in the argument:

# Exercise 3.

Write a new version of the describe-time procedure. Instead of returning a decimal number, it should behave like this:

``````(describe-time 22222)
(6 HOURS 10 MINUTES 22 SECONDS)

(describe-time 4967189641)
(1 CENTURIES 57 YEARS 20 WEEKS 6 DAYS 8 HOURS 54 MINUTES 1 SECONDS)``````

HINT: use `quotient`!

REMINDER: assume 1 year = 365.25 days

# Exercise 4.

As part of computing `(factorial 6)`, Scheme computes `(factorial 2)` and gets the answer 2. After Scheme gets that answer, how does it know what to do next?

# Exercise 5

Here's an example of how the procedure remove-once should work:

``````(remove-once 'morning '(good morning good morning))
(GOOD GOOD MORNING)``````

(It's okay if remove-once removes the other "morning" instead, as long as it removes only one of them.)

Write remove-once.

# Exercise 6.

Write differences, which takes a sentence of numbers as its argument and returns a sentence containing the differences between adjacent elements. (The length of the returned sentence is one less than that of the argument.)

# Exercise 7.

Write a procedure called location that takes two arguments, a word and a sentence. It should return a number indicating where in the sentence that word can be found. If the word isn't in the sentence, return #f. If the word appears more than once, return the location of the first appearance.

# Exercise 8.

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 9.

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.

# Exercise 10.

Write a GPA procedure. It should take a sentence of grades as its argument and return the corresponding grade point average.

Hint: write a helper procedure base-grade that takes a grade as argument and returns 0, 1, 2, 3, or 4, and another helper procedure grade-modifier that returns −.33, 0, or .33, depending on whether the grade has a minus, a plus, or neither.

# Exercise 11.

Write expand, which takes a sentence as its argument. It returns a sentence similar to the argument, except that if a number appears in the argument, then the return value contains that many copies of the following word.

``````(expand '(4 calling birds 3 french hens))
(CALLING CALLING CALLING CALLING BIRDS FRENCH FRENCH FRENCH HENS)``````

# Exercise 12.

Write a predicate same-shape? that takes two sentences as arguments. It should return #t if two conditions are met: The two sentences must have the same number of words, and each word of the first sentence must have the same number of letters as the word in the corresponding position in the second sentence.