Java Reference
In-Depth Information
Pedagogical Note
It is simpler and more efficient to implement the
factorial
method using a loop.
However, we use the recursive
factorial
method here to demonstrate the concept of
recursion. Later in this chapter, we will present some problems that are inherently
recursive and are difficult to solve without using recursion.
If recursion does not reduce the problem in a manner that allows it to eventually converge
into the base case,
infinite recursion
can occur. For example, suppose you mistakenly
write the
factorial
method as follows:
infinite recursion
public static long
factorial(
int
n)
{
return
n *
factorial(n -
1
)
;
}
The method runs infinitely and causes a
StackOverflowError
.
The example discussed in this section shows a recursive method that invokes itself. This is
known as
direct recursion
. It is also possible to create
indirect recursion
. This occurs when
method
A
invokes method
B
, which in turn invokes method
A
. There can even be several more
methods involved in the recursion. For example, method
A
invokes method
B
, which invokes
method
C
, which invokes method
A
.
direct recursion
indirect recursion
20.1
What is a recursive method? What is an infinite recursion?
20.2
How many times is the
factorial
method in Listing 20.1 invoked for
factorial(6)
?
20.3
Show the output of the following programs and identify base cases and recursive calls.
✓
✓
Check
Point
public class
Test {
public static void
main(String[] args) {
System.out.println(
"Sum is "
+ xMethod(
5
));
public class
Test {
public static void
main(String[] args) {
xMethod(
1234567
);
}
}
public static void
xMethod(
int
n) {
if
(n >
0
) {
System.out.print(n %
10
);
xMethod(n /
10
);
public static int
xMethod(
int
n) {
if
(n ==
1
)
return
1
;
else
return
n + xMethod(n -
1
);
}
}
}
}
}
20.4
Write a recursive mathematical definition for computing
2
n
for a positive integer
n
.
20.5
Write a recursive mathematical definition for computing
x
n
for a positive integer
n
and a real number
x
.
20.6
Write a recursive mathematical definition for computing
1
+
2
+
3
+
. . .
+
n
for a
positive integer.
In some cases, recursion enables you to create an intuitive, straightforward, simple
solution to a problem.
Key
Point
The
factorial
method in the preceding section could easily be rewritten without using
recursion. In this section, we show an example for creating an intuitive solution to a problem
using recursion. Consider the well-known Fibonacci-series problem:
