Thinking Recursively with Java

3.1. Factorials

In word games like Scrabble™, the play consists of rearranging a set of letters to form words. For example, given the seven letters

you can construct such words as RIG, SIRE, GRINS, INSERT, or RESTING. Often, there is a considerable advantage in playing as long a word as possible. In Scrabble, for example, playing all seven tiles in the same turn gets you a bonus of fifty points, which makes RESTING or STINGER particularly attractive plays.

In Chapter 6, you will learn how to solve the problem of generating all possible arrangements of a set of letters. For the moment, let's look at the following, somewhat simpler question:

Given a set of seven distinct letters, how many different arrangements would you need to check to discover all possible seven-letter words?

If you think about this problem for a few minutes, you will discover it's not that difficult to solve. In constructing all possible arrangements of seven distinct letters, there are seven possible choices for the starting letter. Once you have chosen the first letter, there are only six ways to choose the next letter in sequence, five ways to choose the third, and so on, until only one letter remains to occupy the last position. Because each of these choices is independent, the total number of orderings is the product of the number of choices at each position. Thus, given seven letters, there are

arrangements, ...