Question 1

Recall the Towers of Hanoi recursive solution for this problem. If there are six disks to move from one Tower to another, how many disk movements would it take to solve the problem using the recursive solution?

Accepted Answer

The recursive solution for the Towers of Hanoi problem requires 2^n - 1 moves for n disks. For 6 disks, it would take 2^6 - 1 = 63 moves.

Question 2

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-Refer to Example Code Ch 12-2: What is returned if factorial(3) is called?

Accepted Answer

When factorial(3) is called, the method checks if x is greater than 1, which is true, so it returns 3 * factorial(2). In turn, factorial(2) checks if its x value is greater than 1, which is also true, so it returns 2 * factorial(1). Finally, factorial(1) checks if its x value is greater than 1, which is false, so it returns 1. Backtracking to factorial(2), it multiplies 2 by the returned value of factorial(1) which is 1, resulting in 2. Backtracking again to factorial(3), it multiplies 3 by the returned value of factorial(2) which is 2, resulting in 6. Thus, the correct answer is D) 6.

Question 3

The difference between direct and indirect recursion is

Accepted Answer

Direct recursion occurs when a method invokes itself, while indirect recursion occurs when there is an intervening method that calls another method in a recursive manner. Choice A accurately describes the difference between the two. The other choices contain incorrect or incomplete information.

Question 4

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
-Refer to Example Code 12-3: What is the result of calling bar(a, 8)?

Accepted Answer

The method bar(a, 8) starts at index 8 of the array a, which contains the value 5. Since it's the last element, the method returns 5 and stops.

Question 5

Recall the Towers of Hanoi recursive solution for this problem. The solution to the Towers of Hanoi has a(n) __________ complexity.

Accepted Answer

The Towers of Hanoi problem has an exponential complexity, specifically O(2^n), where n is the number of disks. This is because each move involves solving two smaller problems and an additional move.

Question 6

Example Code Ch 12-1
Given 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;
}
-Refer to Example Code Ch 12-1: If the method is called as question1_2(8, 3), what is returned?

Accepted Answer

When the method is called question1_2(8,3), it will perform the following recursive calls:
question1_2(7,3) + 1
question1_2(6,3) + 1
question1_2(5,3) + 1
question1_2(4,3) + 1
question1_2(3,3) + 1
Since x == y when x = 3, the method returns 0 and the recursion stops.
Therefore, the final result is: 1+1+1+1+0 = 4. 
Adding the original invocation of the method, the answer is 4+1= 5. 
Therefore, the correct answer is C.

Question 7

Example Code Ch 12-1
Given 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;
}
-Refer to Example Code Ch 12-1: Calling this method will result in infinite recursion if which of the following conditions is initially true?

Accepted Answer

If x is initially less than y, the method will keep calling itself with decreasing x, never reaching the base case where x equals y, resulting in infinite recursion.

Question 8

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-Refer to Example Code Ch 12-2: How many times is the factorial method called with factorial(5)? Include the original method call in your counting.

Accepted Answer

The factorial method is called 5 times in total for factorial(5): the initial call with 5, then recursively with 4, 3, 2, and finally 1.

Question 9

The Koch fractal of order 1 is

Accepted Answer

The Koch fractal of order 1 is a triangle, as it consists of three straight lines forming a equilateral triangle.

Question 10

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-Refer to Example Code Ch 12-2: What is returned if factorial(0) is called?

Accepted Answer

When factorial(0) is called, the if statement will evaluate to false, and the else statement will be executed, returning 1 as the result.

Question 11

Recall the Towers of Hanoi recursive solution for this problem. If there are two disks to move from one Tower to another, how many disk movements would it take to solve the problem using the recursive solution?

Accepted Answer

The Towers of Hanoi problem with two disks requires three moves: move the smaller disk to the intermediate peg, move the larger disk to the target peg, and then move the smaller disk on top of the larger disk on the target peg.

Question 12

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

Accepted Answer

To find the magnitude of a number, we need to keep dividing the number by 10 until the quotient is less than 1. This process can be implemented recursively by dividing x by 10 in each call until x is less than 1. Therefore, the correct answer is D) magnitude(x / 10) + 1.

Question 13

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
-Refer to Example Code 12-3: What is the result of calling foo(a, 2, 9)?

Accepted Answer

The call foo(a, 2, 9) immediately returns 0 because the base case is met (j is not less than a.length, which is 9).

Question 14

What can be said about the difference or similarity, if any, between an infinite loop and an infinite recursion?

Accepted Answer

Both an infinite loop and an infinite recursion continue to repeat indefinitely without any stopping condition. However, the manner in which they repeat is different - an infinite loop is achieved through repeating a block of code within a function or program, while an infinite recursion is achieved by a function repeatedly calling itself without any stopping condition. It is possible to detect both during execution, but it can be more difficult to detect an infinite recursion as it may not always cause a program to crash or result in a runtime error.

Question 15

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
-Refer to Example Code 12-3: What is the result of calling bar(a, 0)?

Accepted Answer

The method bar(a, 0) recursively sums all elements of the array a. The sum of the elements in the array {6, 2, 4, 6, 2, 1, 6, 2, 5} is 34.

Question 16

Example Code Ch 12-4
The following recursive method recognizes whether a String parameter consists of a specific pattern and returns true if the String has that pattern, false otherwise.
public boolean patternRecognizer(String a)
{
if (a == null) return false;
else if (a.length() == 1 || (a.length() == 2
&& a.charAt(0) == a.charAt(1)))
return true;
else if )
return false;
else if )
return patternRecognizer);
else return false;
}
-Refer to Example Code Ch 12-4: Which String of the following would result in patternRecognizer returing true?

Accepted Answer

The answer of Example Code Ch 12-4
The following recursive method...

Question 17

Each time the order of a Koch fractal increases by one, the number of straight line segments

Accepted Answer

Each time the order of a Koch fractal increases by one, the number of straight line segments increases by a factor of four. This is because each line segment in the fractal is replaced by four new segments that form a smaller copy of the original shape.

Question 18

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
-Refer to Example Code 12-3: What is the result of calling foo(a, 2, 0)?

Accepted Answer

The answer of Example Code Ch 12-3
Given the two recursive...

Question 19

Example Code Ch 12-2
Given the following recursive factorial method:
public int factorial(int x)
{
if (x > 1) return x * factorial (x - 1);
else return 1;
}
-Refer to Example Code Ch 12-2: What condition defines the base case for this method?

Accepted Answer

The base case for the factorial method is when x is less than or equal to 1, as the method returns 1 in this scenario, stopping further recursion.

Question 20

Example Code Ch 12-3
Given the two recursive methods shown below, foo and bar.
Assume int[] a = {6, 2, 4, 6, 2, 1, 6, 2, 5}
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[j] + bar(a, j+1);
else return 0;
}
-Refer to Example Code 12-3: What is the result of calling foo(a, 3, 0)?

Accepted Answer

The method foo is designed to count how many times the value of b appears in the array a, starting from index j. Since the value 3 does not appear in the array a = {6, 2, 4, 6, 2, 1, 6, 2, 5}, the method will return 0.

Quiz 12: Recursion

Recall the Towers of Hanoi recursive solution for this problem. If there are six disks to move from one Tower to another, how many disk movements would it take to solve the problem using the recursive solution?

Example Code Ch 12-2 Given the following recursive factorial method: public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -Refer to Example Code Ch 12-2: What is returned if factorial(3) is called?

The difference between direct and indirect recursion is

Recall the Towers of Hanoi recursive solution for this problem. The solution to the Towers of Hanoi has a(n) __________ complexity.

Example Code Ch 12-1 Given 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; } -Refer to Example Code Ch 12-1: If the method is called as question1_2(8, 3) , what is returned?

Example Code Ch 12-1 Given 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; } -Refer to Example Code Ch 12-1: Calling this method will result in infinite recursion if which of the following conditions is initially true?

The Koch fractal of order 1 is

Example Code Ch 12-2 Given the following recursive factorial method: public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -Refer to Example Code Ch 12-2: What is returned if factorial(0) is called?

Recall the Towers of Hanoi recursive solution for this problem. If there are two disks to move from one Tower to another, how many disk movements would it take to solve the problem using the recursive solution?

What can be said about the difference or similarity, if any, between an infinite loop and an infinite recursion?

Each time the order of a Koch fractal increases by one, the number of straight line segments

Example Code Ch 12-2 Given the following recursive factorial method: public int factorial(int x) { if (x > 1) return x * factorial (x - 1) ; else return 1; } -Refer to Example Code Ch 12-2: What condition defines the base case for this method?