Question 1

Consider the following code snippet: public static boolean isEven(int n)
{
If (n % 2 == 0)
{
Return true;
}
Else
{
Return (isOdd(n));
}
}
Public static boolean isOdd(int n)
{
If (n % 2 == 1)
{
Return true;
}
Else
{
Return (isEven(n));
}
}
For any given value of n, what is the maximum number of function calls that could occur?

Accepted Answer

The maximum number of function calls that could occur is 2. This is because the isEven function calls the isOdd function, and the isOdd function calls the isEven function.

Question 2

Backtracking _____.

Accepted Answer

Backtracking starts with a partial solution and incrementally builds it up, exploring possibilities and abandoning paths that do not lead to a valid solution.

Question 3

Complete the following code snippet, which is intended to determine if a value is even or odd using mutual recursion: public static boolean isEven(int n)
{
If (n == 0)
{
Return true;
}
Else
{
Return isOdd(Math.abs(n) - 1);
}
}
Public static boolean isOdd(int n)
{
If (n == 0)
{
_________
}
Else
{
Return isEven(Math.abs(n) - 1);
}
}

Accepted Answer

The base case for determining if a number is odd is when n equals 0, it should return false, as 0 is not odd.

Question 4

Consider the mutually recursive methods below. Select the method call that could be used to generate the output sequence: A5 B4 A3 B2 A1 public static void methodA(int value)
{
If (value > 0)
{
System.out.print(" A" + value);
MethodB(value - 1);
}
}
Public static void methodB(int value)
{
If (value > 0)
{
System.out.print(" B" + value);
MethodA(value - 1);
}
}

Accepted Answer

The sequence starts with "A5", which indicates that methodA is called first with the value 5. The methods then recursively call each other, decrementing the value each time, producing the sequence A5 B4 A3 B2 A1.

Question 5

Consider the following change to the PermutationGenerator class from the textbook. Instead of adding the removed character to the front of the each permutation of the simpler word, we will add it to the end. // Add the removed character to the end of
// each permutation of the simpler word
For (String s : shorterWordPermutations)
{
Result.add(s + word.charAt(i));
}
Consider the list produced by the modified PermutationGenerator. Which best describes this list?

Accepted Answer

The modified method still generates all permutations of the word, just in a different order. Adding the character to the end instead of the front does not omit any permutations.

Question 6

Recursion does NOT take place if any of the following happen:
I method A calls method B, which calls method C, which calls method B
II method A calls method B, which calls method A
III method A calls method B, B returns, and A calls B again

Accepted Answer

The answer of Recursion does NOT take place if any...

Question 7

Which of the following statements about recursion is correct?

Accepted Answer

Recursive solutions can often be more intuitive and easier to understand than iterative ones, especially for problems that have a natural recursive structure, like tree traversals or factorial calculations.

Question 8

____ is a problem-solving technique that examines partial solutions, abandons unsuitable ones, and returns to consider other candidate solutions.

Accepted Answer

Backtracking is a problem-solving technique that involves exploring partial solutions, abandoning those that are unsuitable, and returning to consider other candidate solutions.

Question 9

The method below generates all substrings of a String passed as argument. Assuming that the string contains no duplicate characters, select the statement to complete the method so that it prints all substrings correctly. public static void printSubstrings(String word)
{
If (word.length() > 0)
{
For (int j = 1; j <= word.length(); j++) // print substrings that begin
{ // with the first character
System.out.println(word.substring(0, j));
}
___________________________________ // print substrings without
} // the first character
}

Accepted Answer

The correct answer is B because the substring(1) method creates a new string that starts from the second character of the original string. This ensures that all substrings without the first character are printed.

Question 10

Recursion will take place if any of the following happen:
I method A calls method B, which calls method C
II method A calls method B, which calls method A
III method A calls method A

Accepted Answer

Recursion occurs when a method calls itself directly or indirectly. In II, method A indirectly calls itself through method B. In III, method A directly calls itself.

Quiz 13: Recursion

Backtracking _____.

Recursion does NOT take place if any of the following happen: I method A calls method B, which calls method C, which calls method B II method A calls method B, which calls method A III method A calls method B, B returns, and A calls B again

Which of the following statements about recursion is correct?

____ is a problem-solving technique that examines partial solutions, abandons unsuitable ones, and returns to consider other candidate solutions.

Recursion will take place if any of the following happen: I method A calls method B, which calls method C II method A calls method B, which calls method A III method A calls method A