Java Reference
In-Depth Information
Programming Tip:
Debugging a recursive method
If a recursive method does not work, answer the following questions. Any “no” answers
should guide you to the error.
Does the method have at least one input value?
●
Does the method contain a statement that tests an input value and leads to different cases?
●
Did you consider all possible cases?
●
Does at least one of these cases cause at least one recursive call?
●
Do these recursive calls involve smaller arguments, smaller tasks, or tasks that get closer to
the solution?
●
If these recursive calls produce or return correct results, will the method produce or return a
correct result?
●
Is at least one of the cases a base case that has no recursive call?
●
Are there enough base cases?
●
Does each base case produce a result that is correct for that case?
●
If the method returns a value, does each of the cases return a value?
●
7.14
Our previous examples were simple so that you could study the construction of recursive methods.
Since you could have solved these problems iteratively with ease, should you actually use their
recursive solutions? Nothing is inherently wrong with these recursive methods. However, given the
way that typical present-day systems execute recursive methods, a stack overflow is likely for large
values of
n
. Iterative solutions to these simple examples would not have this difficulty and are easy
to write. Realize, however, that future computing systems might be able to execute these recursive
methods without difficulty.
Later in this topic we will talk about searching an array for a particular item. We will also look at
algorithms that
sort
, or arrange, the items in an array into either ascending or descending order.
Some of the more powerful searching and sorting algorithms often are stated recursively. In this
section, we will process arrays recursively in ways that will be useful to us later. We have chosen a
simple task—displaying the integers in an array—for our examples so that you can focus on the
recursion without the distraction of the task. We will consider more-complex tasks later in this topic
and in the exercises at the end of this chapter.
VideoNote
Using recursion to solve
problems
7.15
Suppose that we have an array of integers and we want a method that displays it. So that we can
display all or part of the array, the method will display the integers in the array elements whose
indices range from
first
through
last
. Thus, we can declare the method as follows:
/** Displays the integers in an array.
@param array an array of integers
@param first the index of the first element displayed
@param last the index of the last element displayed,
0 <= first <= last < array.length */
public static void
displayArray(
int
[] array,
int
first,
int
last)
This task is simple and could readily be implemented using iteration. You might not imagine,
however, that we could also implement it recursively in a variety of ways. But we can and will.
