Java Reference
In-Depth Information
Theorem 7.3
The algorithm printDecimal shown in Figure 7.2 correctly prints n in base 10.
Proof
Let k be the number of digits in n . The proof is by induction on k .
Basis: If
k
=
1
, then no recursive call is made, and line 7 correctly outputs the one
digit of n .
Inductive Hypothesis: Assume that printDecimal works correctly for all digit
integers. We show that this assumption implies correctness for any digit inte-
ger n . Because , the if statement at line 5 is satisfied for a digit integer n .
By the inductive hypothesis, the recursive call at line 6 prints the first k digits of n .
Then line 7 prints the final digit. Thus if any k digit integer can be printed, then so can
a digit integer. By induction, we conclude that printDecimal works for all k , and
thus all n .
k
1
k
+
1
k
1
k
+
1
k
+
1
This observation leads us to the third fundamental rule of recursion.
3.
“You gotta believe”: Always assume that the recursive call works.
Rule 3 tells us that when we design a recursive method, we do not have to
attempt to trace the possibly long path of recursive calls. As we showed ear-
lier, this task can be daunting and tends to make the design and verification
more difficult. A good use of recursion makes such a trace almost impossible
to understand. Intuitively, we are letting the computer handle the bookkeeping
that, were we to do ourselves, would result in much longer code.
This principle is so important that we state it again: Always assume that
the recursive call works.
The third funda-
mental rule of
recursion: Always
assume that the
recursive call
works. Use this
rule to design your
algorithms.
7.3.3 how it works
Recall that the implementation of recursion requires additional bookkeeping
on the part of the computer. Said another way, the implementation of any
method requires bookkeeping, and a recursive call is not particularly special
(except that it can overload the computer's bookkeeping limitations by calling
itself too many times).
To see how a computer might handle recursion, or, more generally, any
sequence of method calls, consider how a person might handle a super busy
day. Imagine you are editing a file on your computer and the phone rings.
When the house phone rings you have to stop editing the file to deal with the
phone. You might want to write down on a piece of paper what you were
doing to the file, just in case the phone call takes a long time and you can't
remember. Now imagine that while you are on the phone with your spouse,
the cell phone rings. You put your spouse on hold, leaving the phone on a
 
Search WWH ::




Custom Search