Question 1

Some problems are easier to solve recursively than iteratively.

Accepted Answer

Since recursion performs backtracking automatically, any problem that requires backtracking is easier to solve using recursion. Such problems include traversing a maze and searching through a "search space", a topic covered in Artificial Intelligence and Advanced Algorithms courses. In some cases, it is easy to find a recursive solution and so the recursive solution is easier than the iterative solution.

Question 2

Traversing a maze is much easier to do iteratively than recursively.

Accepted Answer

One reason that recursion is appealing is that it automatically backtracks to the point of the last decision. In traversing a maze, when one reaches a dead end, the best place to continue is at the point of the previous intersection (or decision). So, backtracking is performed. To solve a maze iteratively requires implementing a backtracking mechanisms, which is available automatically in recursion.

Question 3

The following two methods will both compute the same thing when invoked with the same value of x. That is, method1(x) = = method2(x).
public int method1(int x)
{
if (x > 0) return method1(x - 1) + 1;
else return 0;
}
public int method2(int x)
{
if (x > 0) return 1 + method2(x - 1);
else return 0;
}

Accepted Answer

The only difference between the two methods is the order of the recursive call and adding 1 to the return value. The difference is denoted by calling the first method head recursive and the second tail recursive. So both methods will compute the same value, but arrive at the value in different ways.

Question 4

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
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 (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
-If the statement a.substring(1, a.length( ) - 1) were changed to be (a.substring(1, a.length( )), then the method would
A) have infinite recursion unless the String were null
B) always return True
C) always return false
D) return True only if all characters of the String were the same
E) return True only the String had only two characters and they were the same

Accepted Answer

D) The original method recursively calls itself with a substring equal to the String minus the first and last characters. This new version would recursively call itself with a substring equal to the String minus the first character. The method would return True if the first character of the String (or substring) equaled the last character. Since the substring for each recursive call is the same as the previous String less the first character, it winds up comparing each character in the String to the last in the String and returning True only if each character of the String equals the last character. This means all of the characters are the same.

Question 5

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

Accepted Answer

D) The current position is (2, 0), so it is not out of bounds or the lower right corner, and the current grid value was a 1, so the path is still valid. Therefore, the first instruction inside theelse statement is executed, calling traverse with (row + 1, column) which represents the next position to the right.

Question 6

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

Accepted Answer

C) When a point in the maze is tried, its value is changed from 1 to 3, but if the end of the maze is found, the current row, column index is changed to 7. So the path is reflected as 7s and the tried but incorrect path is reflected as 3s and any untried parts of the path are reflected as 1s. For this maze, all legal path parts will have been tried before the solution is found, so the path leading to the exit is comprised of 7s and the remaining paths are comprised of 3s.

Question 7

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

Accepted Answer

D) The method must count the number of digits to the left of the decimal point, so it continually divides the value by 10 until the value has no digits to the left of the decimal point (this is the case if value < 1). Each time the value is divided by 10, 1 is added to the return value. 55,555.555 will be divided by 10 five times before it becomes < 1, and thus return 5.

Question 8

A recursive method without a base case leads to infinite recursion.

Accepted Answer

Without the base case, the recursive method calls itself without the ability to stop, and thus leads to infinite recursion.

Question 9

Each time the order of a Koch fractal increases by one, the number of straight line segments
A) increases by a factor of two
B) increases by a factor of three
C) increases by a factor of four
D) is squared
E) is cubed

Accepted Answer

C) Each line segment is replaced by four equal-length line segments each time the order increases by one. So, the total number of straight line segments increases by a factor of four each time the order is increased by one.

Question 10

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

Accepted Answer

C) Since row and grid do not equal the bottom right node in the grid (that is, we haven't found the solution yet), theelse clause, done = traverse(row + 1, column);, is executed, resulting in traverse(1, 0); being called.

Question 11

The difference between direct and indirect recursion is
A) direct recursion occurs when a method invokes itself; indirect recursion occurs when there is an intervening method
B) indirect recursion occurs when a method invokes itself; direct recursion occurs when there is an intervening method
C) direct recursion only occurs with methods declared to be private; indirect recursion can occur with methods declared to be private, protected, or public
D) indirect recursion only occurs with methods declared to be private; direct recursion can occur with methods declared to be private, protected, or public
E) none of the above

Accepted Answer

A) Direct recursion means that a method directly invokes itself with no intervening method. Indirect recursion occurs when there are one or more intervening methods before the original method is invoked again.

Question 12

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
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 (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
-If the method is called as patternRecognizer(x) where x is "aa", what will the result be?
A) True
B) false
C) a NullPointerException
D) a run-time error
E) infinite recursion

Accepted Answer

A) One of the base cases tests to see if the String has 2 characters and if so, returns True if the two characters are the same.

Question 13

An infinite loop and an infinite recursion
A) are different because it is impossible to detect the latter, while it's quite easy to detect the former
B) both continue to repeat indefinitely
C) both will be caught by the compiler
D) both will be caught by the Java Virtual Machine during execution
E) none of the above

Accepted Answer

B) Both infinite loops and recursion are similar in that they continue to repeat indefinitely. Neither can be caught by the compiler or by the runtime (the JVM).
12.2

Question 14

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
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 (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
-What is a fractal?
A) a portion of a larger structure (a fraction)
B) a geometric shape that can be made up of the same pattern repeated at different scales and orientations
C) a recursively defined numeric function
D) a ratio (a fraction)
E) none of the above

Accepted Answer

B) A fractal is a geometric shape that is "self-similar" it appears to be the same regardless of scale and orientation. The same shape appears at different scales and orientations.

Question 15

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
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 (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
-A recursive algorithm is superior to an iterative algorithm along which of the following criteria?
A) The recursive algorithm is easier to debug
B) The recursive algorithm is computationally more efficient
C) The recursive algorithm is more elegant
D) The recursive algorithm requires less memory to execute
E) all of the above

Accepted Answer

C) When comparing most recursive algorithms to their iterative counterparts, it is almost always the case that the recursive algorithm is shorter, so it tackles the same problem with less code. This means it is more elegant (which does not necessarily mean it is easier to understand).

Question 16

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
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 (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
-Aside from writing recursive methods, another way that recursion is often used is to define
A) words in English
B) mathematical functions
C) rules and laws
D) child classes of a parent class in object-oriented programming
E) recursion is used in all of the above

Accepted Answer

B) Mathematics often defines functions recursively for simplicity.

Question 17

The Koch fractal of order 1 is
A) a triangle
B) a square
C) a point
D) a circle
E) none of the above

Accepted Answer

A) The Koch fractal of order 1 is the simplest possible closed figure that contains an area-a triangle.

Question 18

The following method recognizes whether a String parameter consists of a specific pattern and returns True if the String has that pattern, false otherwise. Use this recursive method to answer the questions below.
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 (a.length( ) = = 2 && a.charAt(0) != a.charAt(1) ) return false;
else if (a.charAt(0) == a.charAt(a.length( ) - 1))
return patternRecognizer(a.substring(1, a.length( ) - 1));
else return false;
}
-Which String below would result in patternRecognizer returning True?
A) "abcba"
B) "aaabbb"
C) "abcde"
D) "aabba"
E) all of the above Strings will result in the method returning True

Accepted Answer

A) The method patternRecognizer returns True if the String is a palindrome. This can be seen by analyzing the code. If the String has 1 character, or 2 characters which are equal, it returns True, otherwise if the first and last characters are the same, it recursively calls itself with the substring starting at character 1 and going to the second to last character (so, since in "abcba" the first and last characters are the same, the method is called recursively with the substring "bcb"). Only if the first and last characters do not match is false returned. The only palindrome in the list of options is a, "abcba".

Question 19

The following method lacks a base case.
public int noBaseCase(int x)
{
if (x > 0)
return noBaseCase(x - 1) + 1;
else return noBaseCase(x - 2) + 2;
}

Accepted Answer

A base case is a condition that, when taken, stops the recursion by not calling the method recursively. In the above method, there is a condition, but whether the condition is True or false, the method invokes itself recursively.

Question 20

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

Accepted Answer

D) The value x % y can be computed by continually subtracting y from x until x < y. Then, the result is x. For instance, 7 % 3 = 4 % 3 = 1 % 3 = 1. The code in answer A - C do not compute x mod y and answer E computes mod but uses an iterative solution, not a recursive one.

Quiz 12: Recursion

Some problems are easier to solve recursively than iteratively.

Traversing a maze is much easier to do iteratively than recursively.

The following two methods will both compute the same thing when invoked with the same value of x. That is, method1(x) = = method2(x). public int method1(int x) { if (x > 0) return method1(x - 1) + 1; else return 0; } public int method2(int x) { if (x > 0) return 1 + method2(x - 1); else return 0; }

A recursive method without a base case leads to infinite recursion.

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

The difference between direct and indirect recursion is

An infinite loop and an infinite recursion

The Koch fractal of order 1 is

The following method lacks a base case. public int noBaseCase(int x) { if (x > 0) return noBaseCase(x - 1) + 1; else return noBaseCase(x - 2) + 2; }

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