Question 1

For the questions below, recall the Towers of Hanoi recursive solution.
-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

Accepted Answer

D) The Towers of Hanoi solution requires using the previous solution twice + 1 extra move. To solve it for 1 disk, it takes 1 move. To solve it for 2 disks, it takes using the solution for 1 disk twice + 1 extra move, or 1 move + 1 move + 1 extra move = 3 moves. We capture this in the equation 2ⁿ - 1 where n is the number of disks. For 3 disks this takes 7 moves, for 4 disks this takes 15 moves, for 5 disks this takes 31 moves and for 6 disks this takes 63 moves.

Question 2

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;
}
-What is the result of calling foo(a, 2, 0);?
A) 0
B) 1
C) 2
D) 3
E) 4

Accepted Answer

C) The method foo counts the number of occurrences of the int parameter in the second position in the array starting at the index given as the third parameter. So, foo(a, 2, 0) finds the number of 2s in a. 2 appears 3 times in array a.

Question 3

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

Accepted Answer

B) The method returns True if the third parameter, j, is equal to the length of b but not equal to the length of a. Thus, the method returns True if the third parameter has reached the value indicating the end of array b but not the end of array a so this is True if a is larger than b. If a and b are equal length or if a is shorter than b, false is returned.

Question 4

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-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

Accepted Answer

C) The method is first invoked with factorial(5), which in turn returns 5 * factorial(4), so factorial is invoked again, which in turn returns 4 * factorial(3), so factorial is invoked again, which in turn returns 3 * factorial(2), so factorial is invoked again, which in turn returns 2 * factorial(1), so factorial is invoked again, and finally factorial(1) invokes the base case and returns 1. So, factorial was invoked 5 times.

Question 5

For the questions below, refer to the following recursive factorial method. public int factorial(int x) { if (x > 1) return x * factorial (x - 1); else return 1; } -What condition defines the base case for this method? A) (x > 1) B) (x = = 1) C) (x = = 0) D) (x <= 0) E) (x <= 1)

Accepted Answer

E) The if condition is (x > 1) but this is the recursive case, so the base case is the opposite condition. The opposite of (x > 1) is (x <= 1).

Question 6

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;
 }
-If the method is called as question1_2(8, 3), what is returned?
A) 11
B) 8
C) 5
D) 3
E) 24

Accepted Answer

C) The method computes x - y if x > y. The method works as follows: each time the method is called recursively, it subtracts 1 from x until (x == y) is becomes True, and adds 1 to the return value. So, 1 is added each time the method is called, and the method is called once for each int value between x and y.

Question 7

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;
 }
-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);

Accepted Answer

C) The method will recursively call itself subtracting 2 from x until x = = 0 or x < 0. If x = = 0, then it x - 2 * i == 0 (for some int value i) or x = = 2 * i, so x must be even. Otherwise, the recursion ends when x < 0, meaning that the original x was odd or less than 0.

Question 8

Which of the following recursive methods would execute approximately log ₂ 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);
}

Accepted Answer

D) This method recursively calls itself with n being half its original value. If n starts at 16, the second call has n = 8, the third has n = 4, the fourth has n = 2, the fifth and final call has n = 1. If n starts at 32, it adds one additional call. If we double n again, it only adds 1 more recursive call. This is a log ₂ n behavior.

Question 9

For the questions below, recall the Towers of Hanoi recursive solution.
-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

Accepted Answer

D) The Towers of Hanoi solution requires using the previous solution twice + 1 extra move. To solve it for 1 disk, it takes 1 move. To solve it for 2 disks, it takes using the solution for 1 disk twice + 1, or 1 move + 1 move + 1 move = 3 moves. We capture this in the equation 2ⁿ - 1 where n is the number of disks.

Question 10

For the questions below, recall the Towers of Hanoi recursive solution.
-The solution to the Towers of Hanoi has a(n) ________ complexity.
A) linear
B) polynomial
C) logarithmic
D) exponential
E) bad

Accepted Answer

D) The complexity for Towers of Hanoi is 2ⁿ - 1, which is known as exponential because, as n increases by 1, the number of moves doubles, or the complexity increases exponentially.

Question 11

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;
}
-What is the result of calling foo(a, 2, 9);?
A) 0
B) 1
C) 2
D) 3
E) 4

Accepted Answer

A) The method foo counts the number of occurrences of the int parameter in the second position in the array starting at the index given as the third parameter. So, foo(a, 2, 9) results in the base case being executed immediately because 9 = = a.length and the base case returns 0.

Question 12

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;
}
-What is the result of calling bar(a, 0);?
A) 0
B) 5
C) 6
D) 12
E) 34

Accepted Answer

E) The bar method recursively sums the elements of array a starting at the location of the second parameter. Since the starting point is location 0, this call sums all elements of a (which equals 34).

Question 13

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-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

Accepted Answer

B) With factorial(0), (x > 1) is not True, so the base case is executed and 1 is returned. Therefore, even though ordinarily 0 * value = 0, the factorial(0) is computed as 1.

Question 14

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

Accepted Answer

C) The method does not appropriately handle a negative parameter, such as sum(-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:
public int sum(int x)
{
if (x = = 0) return 0;
else if (x < 0) return -1 * sum(-x);
else return sum(x - 1) + x;
}

Question 15

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;
 }
-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)

Accepted Answer

D) If (x < y) is True initially, then theelse clause is executed resulting in the method being recursively invoked with a value of x - 1, or a smaller value of x, so that (x < y) will be True again, and so for each successive recursive call, (x < y) will be True and the base case, x == y, will never be True.

Question 16

For the questions below, refer to the following recursive factorial method.
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-What is returned if factorial(3) is called?
A) 0
B) 1
C) 3
D) 6
E) 9

Accepted Answer

D) With factorial(3), x > 1, so it returns 3 * factorial(2), with factorial(2), x > 1 so it returns 2 * factorial(1), with factorial(1), 1 is returned, so we have 3 * 2 * 1 = 6.

Question 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

Accepted Answer

C) The recursive case has the method calling itself with the same parameter, and so n does not change, thus if (n > 0) is initially True, it will remain True.

Question 18

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;
}
-What is the result of bar(a, 8);?
A) 0
B) 5
C) 6
D) 12
E) 34

Accepted Answer

B) The bar method recursively sums the elements of array a starting at the location of the second parameter (8 in this case). So, bar(a, 8) sums up only the last element in the array, 5, and so 5 is returned.

Question 19

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;
}
-What is the result of calling foo(a, 3, 0);?
A) 0
B) 1
C) 2
D) 3
E) 4

Accepted Answer

A) The method foo counts the number of occurrences of the int parameter in the second position in the array starting at the index given as the third parameter. So, foo(a, 3, 0) finds the number of 3s in a. There are none.

Question 20

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

Accepted Answer

C) The method compares each character in String a with char b until i reaches the length of String a. 1 is added to the return value for each match.

Quiz 12: Recursion

For the questions below, recall the Towers of Hanoi recursive solution. -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?

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) ; }

For the questions below, refer to the following recursive factorial method. public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -What condition defines the base case for this method?

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; } -If the method is called as question1_2(8, 3) , what is returned?

Which of the following recursive methods would execute approximately log ₂ n times for an initial parameter n?

For the questions below, recall the Towers of Hanoi recursive solution. -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?

For the questions below, recall the Towers of Hanoi recursive solution. -The solution to the Towers of Hanoi has a(n) ________ complexity.

For the questions below, refer to the following recursive factorial method. public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -What is returned if factorial(0) is called?

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; }

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; } -Calling this method will result in infinite recursion if which condition below is initially True?

For the questions below, refer to the following recursive factorial method. public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -What is returned if factorial(3) is called?

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; }

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) ; }