Chapter 12
Recursion
12.1 Selecting Balls with Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
12.1.1 Balls of Two Colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
12.1.2 Balls of Three Colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
12.1.3 A Further Restriction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
12.2 One-Way Streets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
12.3 The Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
12.4 Calculating Integer Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
12.4.1 Count the Number of “1”s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
12.4.2 Odd Numbers Only . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
12.4.3 Increasing Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
12.4.4 Alternating Odd and Even Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
12.4.5 Generalizing the Integer Partition Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
12.4.6 How Not to Solve the Integer Partition Problem . . . . . . . . . . . . . . . . . . . . . 181
Recursion is an everyday phenomenon that is natural to the human mind. Sometimes re-
cursive computer programs can be challenging to reason about; however, recursion itself is
readily understandable. For example, every person has parents, who have parents, who have
parents, etc. That is an example of recursion. For another example, take two mirrors and
make them face each other. A characteristic pattern will appear with images within images
within images, etc. We also see recursion in cell-growth, and this manifests in the shapes
of living things. For example, a tree’s trunk is divided into main branches. Each branch in
turn is further divided into smaller branches. Smaller branches are divided into twigs, and
eventually we have leaves. This is the third example of recursion. In this case the recursive
branching of the trunk into twigs is bounded by the leaves. Recursion is everywhere around
us, and is also part of us. It is part of language, the way we think, and how our bodies grow.
Recursion is one of nature’s ways for solving complex problems.
There are three essential properties of recursion:
1. Recurring patterns. The examples above describe some recurring patterns: a person,
the person’s parents, their parents ...
2. Changes. Recursion does not merely mean repeating. A person is younger than the
parents and they are younger than their parents. In the two mirrors, images become
smaller. For a tree, branches become thinner. Each step of a recursive pattern has a
characteristic change.
3. A terminating condition (or conditions). The recurring pattern eventually stops. A
family tree stops at the youngest member that has no child. The images in the fac-
ing mirrors will become smaller and eventually invisible. When a branch eventually
becomes leaves, the pattern stops.
Recursion can be a strategy for solving problems using a concept called divide and
conquer: Divide a complex problem into smaller problems and solve (conquer) the smaller
problems. This works when the smaller problems are related to the larger problem. Recursion
uses the following steps:
1. Identify the argument (or arguments) of a problem.
165
166 Intermediate C Programming
2. Express the solution based on the arguments.
3. Determine the simple case(s) when the solutions are “obvious”.
4. Derive the relationships between the complex case(s) and the simpler case(s).
Recursion is a topic that often separates beginning programmers from advanced pro-
grammers. Many introductory books treat recursion superficially, giving one or two exam-
ples without really explaining why recursion can be useful and how to use recursion to solve
problems. On the other hand, the books written for advanced programmers assume readers
are already comfortable solving problems with recursion. Thus, neither type of book ex-
plains recursion in detail. Because of this gap, many people find recursion mysterious. This
book gives many examples that explain how to use recursion to solve problems.
12.1 Selecting Balls with Restrictions
12.1.1 Balls of Two Colors
There are unlimited red (R) and blue (B) balls in a bag. A game selects n balls under
the restriction that red balls cannot be selected one after another. The order matters: The
selections RB and BR are considered different from each other. The question is how many
different ways can the balls be selected? This problem can be solved recursively by applying
the four steps above:
1. Identify the argument (or arguments) of the problem.
For this problem, the number of balls, n, is the argument.
2. Express the solution based on the arguments.
Let f (n) be the answer: the number of ways to select the n balls under the restriction
(two adjacent balls cannot both be red).
3. Determine the simple case(s) when the solutions are “obvious”.
If only one ball is selected, then there are two possibilities: R or B . Thus, f(1) is 2. If
only two balls are selected, there are three possibilities: RB, BR, and BB. Therefore,
f(2) is 3.
4. Derive the relationships between the complex case(s) and the simpler case(s).
If there are n balls (n > 2), the first ball can be R or B and vice versa. Therefore, there
are exactly two choices for the first ball. Fig. 12.1 shows the two different scenarios in
the selection of the second ball.
(a) If the first ball is B, then the remaining n − 1 balls must follow the same rule:
no red balls are adjacent. There are f (n − 1) possibilities.
(b) If the first ball is R, then the second ball must be B. A B ball resets the pos-
sibilities since the third ball can be R or B, without any additional restriction.
Therefore the remaining n − 2 balls must follow the same rule and there are
f(n − 2) possibilities.
Based on this analysis, f(n) is the sum f(n − 1) + f (n − 2).
f(n) =
2 when n is 1
3 when n is 2
f(n − 1) + f(n − 2) when n > 2
(12.1)
Recursion 167
FIGURE 12.1: To decide f (n), consider the possibilities for the first ball. If the first ball
is B, the remaining n − 1 balls have f (n − 1) possibilities. If the first ball is R, then the
second ball must be B and the remaining n − 2 balls have f (n − 2) possibilities.
12.1.2 Balls of Three Colors
The question can be extended in many ways. The first extension considers balls of three
colors. We still assume that there are unlimited red (R), green (G), and blue (B) balls. We
select balls under the restriction that two adjacent balls cannot be both red. Note that the
orders matter: RB and BR are different selections. How many possible sequences can be
selected for n balls?
When n is one, there are three possibilities:
1. R
2. G
3. B
When n is two, there are eight possibilities. Please notice that R R is an invalid option.
1. R G
2. R B
3. G R
4. G G
5. G B
6. B R
7. B G
8. B B
What is the number of possibilities for n balls when n > 2? To solve this problem, let
f(n) be the answer. We already know that f(1) = 3 and f(2) = 8.
When n > 2, consider the possibilities for the very first ball. Fig. 12.2 shows three
scenarios:
1. If the first ball is G, then the second ball can be any of the three colors. There is
no further restriction for the remaining n − 1 balls. Thus, there are f(n − 1) possible
sequences for the remaining n − 1 balls.
2. Likewise, if the first ball is B, then the second ball can be any of the three colors.
There is no further restriction for the remaining n−1 balls. There are f(n−1) possible
sequences for the remaining n − 1 balls.
168 Intermediate C Programming
3. If the first ball is R, then there are two scenarios:
(a) If the second ball is G, then the third ball can be any of the three colors. There
is no further restriction for the remaining n − 2 balls. Thus, there are f(n − 2)
possible sequences for the remaining n − 2 balls.
(b) If the second ball is B, then the third ball can be any of the three colors. There
is no further restriction for the remaining n − 2 balls. Thus, there are f(n − 2)
options for the remaining n − 2 balls.
(c) Note that the second ball cannot be R, so this possibility is not considered.
FIGURE 12.2: To decide f (n), consider the possibilities for the first ball. If the first ball
is G or B, the remaining n − 1 balls have f(n − 1) possibilities. If the first ball is R, the
second ball must be G or B and the remaining n − 2 balls have f(n − 2) possibilities.
Thus, the relationships are:
f(n) =
3 if n is 1
8 if n is 2
f(n − 1) + f(n − 1) + f(n − 2) + f(n − 2) = 2f (n − 1) + 2f (n − 2) if n > 2
(12.2)
12.1.3 A Further Restriction
This question can be extended further with another restriction. Now two adjacent balls
cannot both be red or green. Two adjacent balls can both be blue. How many possible
sequences can be selected for n balls? When n is one, there still are three possibilities:
1. R
2. G
3. B
Recursion 169
When n is two, there are seven possibilities. Please notice that G G is an invalid option.
1. R G
2. R B
3. G R
4. G B
5. B R
6. B G
7. B B
We use a different approach to solve this problem, by using some additional functions:
• r(n) is the number of possible sequences when selecting n balls and the first ball is R.
• g(n) is the number of possible sequences when selecting n balls and the first ball is G.
• b(n) is the number of possible sequences when selecting n balls and the first ball is B.
• f (n) is the number of possible sequences when selecting n balls and the first ball can
be any of the three colors. Thus, f(n) = r(n) + g(n) + b(n).
The following table shows the values of these functions for n equal to 1 or 2:
n 1 2
r(n) 1 2
g(n) 1 2
b(n) 1 3
f(n) 3 7
How is r(n) calculated when n is greater than 2? By definition, r(n) means the number
of possible sequences of n balls and the first one is R. For the remaining n −1 balls, the first
ball (the second among the n balls) can be either G or B. If the first (the second among the
n balls) ball is G, there are g(n − 1) possibilities. Similarly, when the first ball (the second
among the n balls) is B, there are b(n−1) options. Thus, r(n) = g(n−1)+b(n−1). Because
the same restrictions apply to both red and green balls, we can use the same reasoning to
write g(n) = r(n − 1) + b(n − 1).
How many possibilities are there when selecting n balls and the first ball is B? When
the first is blue then there is no restriction on the second ball in the sequence. The second
ball can be red, green, or blue; thus, this is true b(n) = g(n − 1) + b(n − 1) + r(n − 1). This
is also f (n − 1) because it means selecting n − 1 balls and the first ball can be G, B, or R.
There are f(n − 1) possible sequences of length n − 1 balls so b(n) = f(n − 1).
The complete solution is shown below:
r(n) = g(n − 1) + b(n − 1)
g(n) = r(n − 1) + b(n − 1)
b(n) = f(n − 1)
f(n) = r(n) + g(n) + b(n)
(12.3)
The table below shows the values when n is between 1 and 6:
n 1 2 3 4 5 6
r(n) 1 2 5 12 29 70
g(n) 1 2 5 12 29 70
b(n) 1 3 7 17 41 99
f(n) 3 7 17 41 99 239
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.