Discrete Mathematics for Computer Science

Strong Form of Mathematical Induction 77

ting TrialFactor equal to 2. Because now Mod(n, TrialFactor) A 0 is FALSE, we call
PrintFactors(2) and PrintFactors(4/2). These two calls to PrintFactors both print a 2,
completing the factorization of 12.
When you trace the execution of a procedure, some visual help to see how control
passes from one step to another can be valuable. In Figure 1.20 we show how 376 is fac-
tored. The while loop determines whether there is a factor for n starting with I/n and
working down to 1. The figure displays the flow of control after the while loop has been
executed. Each time the while loop identifies a factor, it prints the factor and terminates.
This is seen when PrintFactors(2) is executed. If the while loop identifies a factor of n
such that

n = TrialFactor. (n/TrialFactor)

and TrialFactor is greater than 1, then it executes PrintFactors again on both TrialFactor
and n/TrialFactor. This is indicated, for example, in the case of PrintFactors(4) that must
execute both PrintFactors(2) and PrintFactors(4/2) when the while loop identifies 2 as a
factor.

PrintFactors(3 76)

Executes Executes

PrintFactors(8) PrintFactors(47)

Execute / Executes Prints^47

PrintFactors(2) PrintFactors(4)

Prints 2 Execute/ Executes

PrintFactors(2) PrintFactors(2)

Prints 2 Prints 2

Factors: 2, 2, 2, 47

Figure 1.20 Flow of control for PrintFactors(376).

Theorem 4. Prove that the algorithm PrintFactors is correct.

Proof. Exercise for the reader. U

1.10.4 Application: Binary Search

If you think about how you look for a name in a phone book, you will have a good idea
of what the code in the BinarySearch algorithm does. A common process is the following:
You open a phone book to about the page where you think the name should appear. If you
have turned past the name you want, you continue this process with the first part of the
phone book. Otherwise, you have not gone far enough in the phone book, so you continue
this process using the pages from that point forward to the end of the phone book. More
mechanically, you could think of a program always choosing a page halfway through those