Java Reference
In-Depth Information
Pedagogical Note
The recursive implementation of the
fib
method is very simple and straightforward,
but it isn't efficient, since it requires more time and memory to run recursive methods.
See Programming Exercise 18.2 for an efficient solution using loops. Though it is not
practical, the recursive
fib
method is a good example of how to write recursive methods.
18.7
✓
✓
Show the output of the following two programs:
Check
Point
public class
Test {
public static void
main(String[] args) {
xMethod(
5
);
}
public class
Test {
public static void
main(String[] args) {
xMethod(
5
);
}
public static void
xMethod(int n) {
if
(n >
0
) {
System.out.print(n +
" "
);
xMethod(n -
1
);
public static void
xMethod(
int
n) {
if
(n >
0
) {
xMethod(n -
1
);
System.out.print(n +
" "
);
}
}
}
}
}
}
18.8
What is wrong in the following method?
public class
Test {
public static void
main(String[] args) {
xMethod(
1234567
);
}
public class
Test {
public static void
main(String[] args) {
Test test =
new
Test();
System.out.println(test.toString());
}
public static void
xMethod(double n) {
if
(n !=
0
) {
System.out.print(n);
xMethod(n /
10
);
}
}
}
public
Test() {
Test test =
new
Test();
}
}
18.9
How many times is the
fib
method in Listing 18.2 invoked for
fib(6)
?
If you think recursively, you can solve many problems using recursion.
Key
Point
The preceding sections presented two classic recursion examples. All recursive methods have
the following characteristics:
recursion characteristics
The method is implemented using an
if-else
or a
switch
statement that leads to
different cases.
if-else
■
One or more base cases (the simplest case) are used to stop recursion.
base cases
■
Every recursive call reduces the original problem, bringing it increasingly closer to a
base case until it becomes that case.
reduction
■
In general, to solve a problem using recursion, you break it into subproblems. Each sub-
problem is the same as the original problem but smaller in size. You can apply the same
approach to each subproblem to solve it recursively.
Search WWH ::
Custom Search