Recursive Thinking

by rrusczyk, Jun 17, 2006, 3:21 PM

We have the following problem among our Independent Study assignments. It's a great example of using recursive thinking.

On planet Oneletter, the language only has one letter. To write a message in the language, you make 'words' consisting of strings of this one letter, and you separate each word by one space (and one space only). The typewriters on the planet are very simple - the letter and a spacebar. The question is this: find with proof the number of messages that can be generated with 14 keystrokes if there is no space at the beginning or the end of the message.

We start where we almost always start with complicated problems that aren't immediately obvious to us - we play around. We do so by considering shorter messages.

1 keystroke: x. Hurm. 1 message. Pretty uninteresting.

2 keystrokes: xx. 1 message. Not too interesting.

3 keystrokes: xxx, x_x. 2 messages. Now the more experienced reader knows what the next number will be.

4 keystrokes: xxxx, xx_x, x_xx. 3 messages.

This is starting to look like the Fibonacci sequence. If you aren't convinced:

5 keystrokes: xxxxx, xx_xx, x_x_x, xxx_x, x_xxx. 5 messages.

This just has to be Fibonacci - but why?

When we have to show that a sequence is the Fibonacci sequence, usually the easiest way is to show that it starts 1, 1 (we've already done this), then show that it satisfies the recursion $F_n = F_{n-1} + F_{n-2}$ . Or, in terms of this problem, we must show that the number of $n$ -keystroke messages equals the sum of the numbers of $n-1$ and $n-2$ keystroke messages.

We can use our simple cases as a guide to build the recursion since we know what we're looking for. We want to find a method to build the 5 keystroke sequences:

xxxxx, xx_xx, x_x_x, xxx_x, x_xxx

from the 3- and 4-keystroke sequences:

xxx, x_x and xxxx, xx_x, x_xx

We want a method that takes each of the smaller sequences to exactly one of the longer sequences by some rule that we know will always work, e.g. the rule will allow us to make the 12-keystroke sequences from the 10- and 11-keystroke sequences.

The easiest way to make a 5-keystroke from a 4-keystroke is to just add another letter:

xxxx -> xxxxx
xx_x -> xx_xx
x_xx -> x_xxx

That leaves the 3-keystroke sequences. We take a look at the 5-keystroke sequences that are left, and they are the two that end with a space before the x. That gives us our rule for 3-keystroke sequences - just add a space, then an x:

xxx -> xxx_x
x_x -> x_x_x

Clearly, this will always work. Generally speaking, there are two ways we can build an $n$ -keystroke message from smaller messages: either add a single letter to an $n-1$ -keystroke message or add a space then a letter to an $n-2$ -keystroke message. Notice that it is impossible to ever create the same $n$ -keystroke message twice, since every $n-1$ -keystroke messages end in a letter - therefore all the ones generated from $n-1$ -keystroke messages end in 'xx' while those generated from $n-2$ -keystroke messages end in '_x'.

But what if we didn't recognize the Fibonacci sequence? Then, we might have engaged in a little backwards thinking, which is often the heart of building recursions.

We might think 'How can I build a 14-keystroke message from smaller messages?' This makes us think of just cutting a letter off the end of a 14-keystroke message. There are then two possibilities:

(1) The result still ends in a letter. In other words, it is a valid 13-keystroke message.
(2) The result after cutting off a letter ends in a space. Therefore, it must be a 12-keystroke message followed by a space (since we can't have two spaces in a row).

There are no other options - lopping a letter off our 14-keystroke message gets us one or the other. In other words, the number of 14-keystroke messages is just the sum of the numbers of 13-keystroke messages and 12-keystroke messages.

But there's nothing special about 14! This will work for any number (after the first two, of course). So, if we let $F_n$ be the number of $n$ -keystroke messages, we have $F_n = F_{n-1} + F_{n-2}$ . As we already showed, $F_1=F_2=1$ , so we have the Fibonacci sequence!

The Fibonacci sequence is one of the best tools for teaching recursive thinking because it can be cast in so many different forms. I invite the readers to please add your own Fibonacci problems for beginners to try to figure out why the problems result in the Fibonacci sequence.

I offer my own basic extensions of the problem above to students new to recursion:
(1) What if the language on Planet OneLetter is OneLetterUptoTwoSpaces, meaning that there can be either one or two spaces between words?
(2) What if the language is OneLetterJustTwoSpaces, meaning that between any two words there must be two spaces?

How many n-keystroke messages can be formed in each case?

Comment