Java Reference
In-Depth Information
/
**
ComputethemovestosolveaTowerofHanoipuzzle.
Functionmovedoes(orprints)theactualmoveofadisk
fromonepoletoanother.
@paramnThenumberofdisks
@paramstartThestartpole
@paramgoalThegoalpole
@paramtempTheotherpole
*
/
staticvoidTOH(intn,Polestart,Polegoal,Poletemp){
if(n==0)return; //Basecase
TOH(n-1,start,temp,goal);//Recursivecall:n-1rings
move(start,goal); //Movebottomdisktogoal
TOH(n-1,temp,goal,start);//Recursivecall:n-1rings
}
Those who are unfamiliar with recursion might find it hard to accept that it is
used primarily as a tool for simplifying the design and description of algorithms.
A recursive algorithm usually does not yield the most efficient computer program
for solving the problem because recursion involves function calls, which are typi-
cally more expensive than other alternatives such as a
while
loop. However, the
recursive approach usually provides an algorithm that is reasonably efficient in the
sense discussed in Chapter 3. (But not always! See Exercise 2.11.) If necessary,
the clear, recursive solution can later be modified to yield a faster implementation,
as described in Section 4.2.4.
Many data structures are naturally recursive, in that they can be defined as be-
ing made up of self-similar parts. Tree structures are an example of this. Thus,
the algorithms to manipulate such data structures are often presented recursively.
Many searching and sorting algorithms are based on a strategy of divide and con-
quer. That is, a solution is found by breaking the problem into smaller (similar)
subproblems, solving the subproblems, then combining the subproblem solutions
to form the solution to the original problem. This process is often implemented
using recursion. Thus, recursion plays an important role throughout this topic, and
many more examples of recursive functions will be given.
2.6
Mathematical Proof Techniques
Solving any problem has two distinct parts: the investigation and the argument.
Students are too used to seeing only the argument in their textbooks and lectures.
But to be successful in school (and in life after school), one needs to be good at
both, and to understand the differences between these two phases of the process.
To solve the problem, you must investigate successfully. That means engaging the
problem, and working through until you find a solution. Then, to give the answer
to your client (whether that “client” be your instructor when writing answers on
a homework assignment or exam, or a written report to your boss), you need to
be able to make the argument in a way that gets the solution across clearly and
