Java Reference
In-Depth Information
if (first == last)
System.out.println(array[first] + " ");
else
{
int mid = first + (last - first) / 2;
// Note the order of the records pushed onto the stack
programStack.push( new Record(mid + 1, last));
programStack.push( new Record(first, mid));
} // end if
} // end while
} // end displayArray
This approach does not always produce an elegant solution. We certainly could write an iterative
version of displayArray that was easier to understand than this version and did not require a stack. But
sometimes a simple iterative solution is not apparent; in such cases, the stack approach offers a possible
solution. You will see a more useful example of a stack-based iteration in Segment 24.14 of Chapter 24.
C HAPTER S UMMARY
Recursion is a problem-solving process that breaks a problem into identical but smaller problems.
The definition of a recursive method must contain logic that involves an input—often a parameter—to the method
and leads to different cases. One or more of these cases are base cases, or stopping cases, because they provide a
solution that does not require recursion. One or more cases include a recursive invocation of the method that takes
a step toward a base case by solving a “smaller” version of the task performed by the method.
For each call to a method, Java records the values of the method's parameters and local variables in an acti-
vation record. The records are placed into an ADT called a stack that organizes them chronologically. The
record most recently added to the stack is of the currently executing method. In this way, Java can suspend
the execution of a recursive method and invoke it again with new argument values.
A recursive method that processes an array often divides the array into portions. Recursive calls to the
method work on each of these array portions.
A recursive method that processes a chain of linked nodes needs a reference to the chain's first node as its parameter.
A recursive method that is part of an implementation of an ADT often is private, because its use requires
knowledge of the underlying data structure. Although such a method is unsuitable as an ADT operation, it
can be called by a public method that implements the operation.
A recurrence relation expresses a function in terms of itself. You can use a recurrence relation to describe the
work done by a recursive method.
Any solution to the Towers of Hanoi problem with n disks requires at least 2 n - 1 moves. A recursive solution to this
problem is clear and as efficient as possible. As an O(2 n ) algorithm, however, it is practical for small values of n .
Each number in the Fibonacci sequence—after the first two—is the sum of the previous two numbers. Computing a
Fibonacci number recursively is quite inefficient, as the required previous numbers are computed several times each.
Tail recursion occurs when the last action of a recursive method is a recursive call. This recursive call per-
forms a repetition that can be done by using iteration. Converting a tail-recursive method to an iterative one
is usually a straightforward process.
Indirect recursion results when a method calls a method that calls a method, and so on until the first method
is called again.
You can use a stack instead of recursion to implement a recursive algorithm. This stack mimics the behavior
of the program stack.
 
Search WWH ::




Custom Search