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) ?
18.4 Problem Solving Using Recursion
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