18 Recursion
Objectives
In this chapter you’ll:
■Learn the concept of
recursion.
■Write and use recursive
methods.
■Determine the base case and
recursion step in a recursive
algorithm.
■Learn how recursive method
calls are handled by the
Self-Review Exercises 2
Self-Review Exercises
18.1 State whether each of the following is true or false. If false, explain why.
a) A method that calls itself indirectly is not an example of recursion.
b) Recursion can be efficient in computation because of reduced memory-space usage.
c) When a recursive method is called to solve a problem, it actually is capable of solving
only the simplest case(s), or base case(s).
d) To make recursion feasible, the recursion step in a recursive solution must resemble the
original problem, but be a slightly larger version of it.
18.2 A is needed to terminate recursion.
a) recursion step
b) break statement
c) void return type
d) base case
18.3 The first call to invoke a recursive method is .
a) not recursive
b) recursive
c) the recursion step
d) none of the above
18.4 Each time a fractal’s pattern is applied, the fractal is said to be at a new .
a) width
b) height
c) level
d) volume
18.5 Iteration and recursion each involve a(n) .
a) iteration statement
b) termination test
c) counter variable
d) none of the above
18.6 Fill in the blanks in each of the following statements:
a) The ratio of successive Fibonacci numbers converges on a constant value of 1.618…, a
number that has been called the or the .
b) Iteration normally uses an iteration statement, whereas recursion normally uses a(n)
statement.
c) Fractals have a(n) property—when subdivided into parts, each is a reduced-
size copy of the whole.
3Chapter 18 Recursion
Exercises
NOTE: Solutions to the programming exercises are located in the ch18solutions folder.
Each exercise has its own folder named ex18_## where ## is a two-digit number represent-
ing the exercise number. For example, exercise 18.17’s solution is located in the folder ex-
18_17.
18.7 What does the following code do?
18.8 Find the error(s) in the following recursive method, and explain how to correct it (them).
This method should find the sum of the values from 0 to n.
1public int mystery(int a, int b) {
2 if (b == 1) {
3 return a;
4 }
5 else {
6 return a + mystery(a, b – 1);
7 }
8}
1public int sum(int n) {
2 if (n == 0) {
3 return 0;
4 }
5 else {
6 return n + sum(n);
7 }
8}
© 2018 Pearson Education, Inc., 330 Hudson Street, NY NY 10013. All rights reserved.
Exercises 4
18.12 What does the following program do?
18.13 What does the following program do?
1// Exercise 18.12: MysteryClass.java
2public class MysteryClass {
3 public static int mystery(int[] array2, int size) {
4 if (size == 1) {
5 return array2[0];
6 }
7 else {
8 return array2[size – 1] + mystery(array2, size – 1);
9 }
10 }
11
12 public static void main(String[] args) {
13 int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
14
15 int result = mystery(array, array.length);
16 System.out.printf(“Result is: %d%n”, result);
17 }
18 }
1// Exercise ANS: : SomeClass.java
2public class SomeClass {
3 public static String someMethod(int[] array2, int x)
4 if (x < array2.length) {
5 return String.format(
6 “%s%d “, someMethod(array2, x + 1), array2[x]);
7 }
8 else {
9 return “”;
10 }
11 }
12
13 public static void main(String[] args) {
14 int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
15 String results = someMethod(array, 0);
16 System.out.println(results);
17 }
18 }
© 2018 Pearson Education, Inc., 330 Hudson Street, NY NY 10013. All rights reserved.