Java Software Solutions, 8e, Global Edition (Lewis/Loftus)
Chapter 12 Recursion
12.1 Multiple-Choice Questions
For the questions below, use the following recursive method.
public int question1_2(int x, int y)
{
if (x == y) return 0;
else return question1_2(x-1, y) + 1;
}
1) If the method is called as question1_2(8, 3), what is returned?
A) 11
B) 8
C) 5
D) 3
E) 24
2) Calling this method will result in infinite recursion if which condition below is initially true?
A) (x = = y)
B) (x != y)
C) (x > y)
D) (x < y)
E) (x = = 0 && y != 0)
3) The following method should return true if the int parameter is even and either positive or 0,
and false otherwise. Which set of code should you use to replace … so that the method works
appropriately?
public boolean question3(int x) { … }
A) if (x = = 0) return true;else if (x < 0) return false;else return question3(x – 1);
B) if (x = = 0) return false;else if (x < 0) return true;else return question3(x – 1);
C) if (x = = 0) return true;else if (x < 0) return false;else return question3(x – 2);
D) if (x = = 0) return false;else if (x < 0) return true;else return question3(x – 2);
E) return(x = = 0);
}
4) What is returned if factorial(3) is called?
A) 0
B) 1
C) 3
D) 6
E) 9
5) What is returned if factorial(0) is called?
A) 0
B) 1
C) 2
D) nothing, factorial(0) causes infinite recursion
E) nothing, factorial(0) produces a run-time error
6) How many times is the factorial method invoked if originally called with factorial(5)? Include
the original method call in your counting.
A) 1
B) 4
C) 5
D) 6
E) 7
7) What condition defines the base case for this method?
A) (x > 1)
B) (x = = 1)
C) (x = = 0)
D) (x <= 0)
E) (x <= 1)
8) What is wrong with the following recursive sum method? The method is supposed to sum up
the values between 1 and x (for instance, sum(5) should be 5 + 4 + 3 + 2 + 1 = 15).
public int sum(int x)
{
if (x = = 0) return 0;
else return sum(x – 1) + x;
}
A) the base case should return 1 instead of 0
B) the recursive case should return sum(x – 1) + 1; instead of sum(x – 1) + x;
C) the base case condition should be (x <= 0) instead of (x = = 0)
D) the recursive case should return sum(x) + 1;
E) the method should return a boolean instead of an int
5). The result is infinite recursion. We might define a negative parameter as something that
should return 0, or allow a negative parameter to compute a negative sum as in:
9) What does the following method compute? Assume the method is called initially with i = 0
public int question9(String a, char b, int i)
{
if (i = = a.length( )) return 0;
else if (b = = a.charAt(i)) return question9(a, b, i+1) + 1;
else return question9(a, b, i+1);
}
A) the length of String a
B) the length of String a concatenated with char b
C) the number of times char b appears in String a
D) returns 1 if char b appears in String a at least once, and 0 otherwise
E) the char which appears at location i in String a
10) Which of the following recursive methods would execute approximately log 2 n times for an
initial parameter n?
A) public void logcode(int n)
{
if (n > 1) logcode(n – 1);
}
B) public void logcode(int n)
{
if (n > 2) logcode(n – 2);
}
C) public void logcode(int n)
{
if (n > 0) logcode(0);
}
D) public void logcode(int n)
{
if (n > 1) logcode(n / 2);
}
E) public void logcode(int n)
{
if (n > 1) logcode(n – 1 /2);
}
5
© Pearson Education Limited, 2015
For the questions below, assume that int[ ] a = {6, 2, 4, 6, 2, 1, 6, 2, 5} and consider the two
recursive methods below foo and bar.
public int foo(int[ ] a, int b, int j)
{
if (j < a.length)
if (a[j] != b) return foo (a, b, j+1);
else return foo (a, b, j+1) + 1;
else return 0;
}
public int bar(int[ ] a, int j)
{
if (j < a.length)
return a[I] + bar(a, j+1);
else return 0;
}
11) What is the result of calling foo(a, 2, 0);?
A) 0
B) 1
C) 2
D) 3
E) 4
12) What is the result of calling foo(a, 3, 0);?
A) 0
B) 1
C) 2
D) 3
E) 4
13) What is the result of calling foo(a, 2, 9);?
A) 0
B) 1
C) 2
D) 3
E) 4
14) What is the result of calling bar(a, 0);?
A) 0
B) 5
C) 6
D) 12
E) 34
15) What is the result of bar(a, 8);?
A) 0
B) 5
C) 6
D) 12
E) 34
16) What does the following recursive method determine?
public boolean question16(int[ ]a, int[ ] b, int j)
{
if (j = = a.length) return false;
else if (j = = b.length) return true;
else return question16(a, b, j+1);
}
A) returns true if a and b are equal in size, false otherwise
B) returns true if a is larger than b, false otherwise
C) returns true if b is larger than a, false otherwise
D) returns true if a and b have no elements
E) returns the length of array a + length of array b
17) Why is the following method one which has infinite recursion?
public int infiniteRecursion(int n)
{
if (n > 0) return infiniteRecursion(n) + 1;
else return 0;
}
A) Because there is no base case
B) Because the base case will never be true
C) Because the recursive call does not move the parameter closer to the base case
D) Because the recursive call moves the problem further away from the base case
E) None of the above, there is no infinite recursion in this method
18) If there are 2 disks to move from one Tower to another, how many disk movements would it
take to solve the problem using the recursive solution?
A) 0
B) 1
C) 2
D) 3
E) 4
19) If there are 6 disks to move from one Tower to another, how many disk movements would it
take to solve the problem using the recursive solution?
A) 6
B) 13
C) 31
D) 63
E) 127
20) The solution to the Towers of Hanoi has a(n) ________ complexity.
A) linear
B) polynomial
C) logarithmic
D) exponential
E) bad
21) Which of the following methods would properly compute the value of x % y (x mod y)
recursively, assuming that x and y not negative numbers?
A) public int recursiveMod(int x, int y)
{
if (x < y) return y;
else return recursiveMod(x, y – x);
}
B) public int recursiveMod(int x, int y)
{
if (x == y) return 0;
else return recursiveMod(x – y, y) + 1;
}
C) public int recursiveMod(int x, int y)
{
if (x < y) return x;
else return recursiveMod(x – y, y) + 1;
}
D) public int recursiveMod(int x, int y)
{
if (x < y) return x;
else return recursiveMod(x – y, y);
}
E) public int recursiveMod(int x, int y)
{
while (x > y)
x = x – y;
return x;
}
10
© Pearson Education Limited, 2015
For the questions below, consider the following representation of grid and the maze code from
Chapter 11.
Grid:
1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
Code:
public boolean traverse(int row, int column)
{
if (valid(row, column))
{
boolean done = false;
grid[row][column] = TRIED;
if (row == grid.length – 1 && column == grid[0].length – 1)
done = true;
else
{
done = traverse(row + 1, column);
if (!done) done = traverse(row, column + 1);
if (!done) done = traverse(row – 1, column);
if (!done) done = traverse(row, column – 1);
}
if (done) grid[row][column] = PATH;
}
return done;
}
Assume valid returns true if row and column are >= 0 and <= the grid’s row length or column
length and the entry at this position = = 1. And assume TRIED = 3 and PATH = 7
22) If traverse is first called with traverse(0, 0); what will the first recursive call of traverse be?
A) traverse(0, 0);
B) traverse(0, 1);
C) traverse(1, 0);
D) traverse(1, 1);
E) traverse(0, -1);
23) Assume at some point in processing, grid’s row 0 has become 3 3 3 1 1 1 0 0. Which
direction will next be tried?
A) up
B) down
C) left
D) right
E) none, the recursion ends at this point
24) Which of the following grids would be the result after traverse has completed all of its
recursive calls?
A) 1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 1
B) 3 3 3 3 3 3 0 0
0 0 3 0 0 3 0 0
0 0 3 0 0 3 3 0
0 0 3 3 0 0 3 0
0 0 0 3 3 0 0 0
0 0 0 0 3 3 3 3
C) 7 7 7 3 3 3 0 0
0 0 7 0 0 3 0 0
0 0 7 0 0 3 3 0
0 0 7 7 0 0 3 0
0 0 0 7 7 0 0 0
0 0 0 0 7 7 7 7
D) 7 7 7 7 7 7 0 0
0 0 3 0 0 7 0 0
0 0 3 0 0 7 7 0
0 0 3 3 0 0 7 0
0 0 0 3 3 0 0 0
0 0 0 0 3 3 3 3
E) 3 3 3 7 7 7 0 0
0 0 3 0 0 7 0 0
0 0 3 0 0 7 7 0
0 0 3 3 0 0 7 0
0 0 0 3 3 0 0 0
0 0 0 0 3 3 3 3
25) Define the magnitude of a number as the location of the decimal point from the left of the
number (that is, if a number has 4 digits followed by the decimal point, it will have a magnitude
of 4). 100 would then have a magnitude of 3 and 55,555.555 would have a magnitude of 5. A
partial recursive method is given below to compute a positive int parameter’s magnitude. Which
answer below is needed to complete the method?
public int magnitude(double x)
{
if (x < 1) return 0;
else return _______;
}
A) magnitude(x – 1) + 10;
B) magnitude(x – 10) + 1;
C) magnitude(x / 10) + 10;
D) magnitude(x / 10) + 1;
E) magnitude(x / 10) * 2;