Question 1

A recursive solution can have more than one base cases.

Accepted Answer

A recursive solution can have one or more base cases depending on the problem and the implementation. The base case(s) define the point(s) where the recursion stops and returns the result(s).

Question 2

In the recursive solution to the Towers of Hanoi problem,the number of disks to move ______ at each recursive call.
A)decreases by 1
B)increases by 1
C)decreases by half
D)increases by half

Accepted Answer

In the Towers of Hanoi problem, we have to move all the disks from one pole to another. To move n disks from a source pole to a destination pole, we have to first move n-1 disks from the source pole to the auxiliary pole. After that, we can move the largest disk from the source pole to the destination pole, and then move the n-1 disks from the auxiliary pole to the destination pole. This process is repeated recursively until all the disks are moved to the destination pole. As we can see, the number of disks to move decreases by 1 at each recursive call.

Question 3

The binary search algorithm can be applied to an unsorted array.

Accepted Answer

The binary search algorithm can only be applied to a sorted array. If the array is unsorted, the algorithm will not work correctly and may give incorrect results.

Question 4

A recursive solution that finds the factorial of n generates ______ recursive calls.
A)n-1
B)n
C)n+1
D)n*2

Accepted Answer

The recursive solution for finding the factorial of n will make n recursive calls to itself since we need to multiply n with (n-1)!, which involves computing (n-1)!. This process will repeat until we hit the base case of 0 or 1. Therefore, the number of recursive calls will be equal to n.

Question 5

In the Fibonacci sequence,which of the following integers comes after the sequence 1,1,2,3?
A)3
B)4
C)5
D)6

Accepted Answer

In the Fibonacci sequence, each number is the sum of the two preceding ones. So, the next number after 1,1,2,3 will be the sum of 2 and 3, which is 5. Therefore, the answer is choice C.

Question 6

An iterative method always calls itself.

Accepted Answer

An iterative method uses loops to repeat a block of code, unlike a recursive method which calls itself.

Question 7

Every recursive method must have a base case.

Accepted Answer

Every recursive method must have a base case to prevent infinite recursion. The base case is the scenario where the function stops calling itself and returns a value.

Question 8

When constructing a recursive solution,you should assume that a recursive call's postcondition is true if its precondition is true.

Accepted Answer

This assumption is known as the "Recursive Leap of Faith". It allows the programmer to focus on the base case and assume that the recursive calls will eventually reach the base case and return the correct result.

Question 9

The base case for a recursive solution to the kth smallest item problem cannot be predicted in advance.

Accepted Answer

The base case for a recursive solution to the kth smallest item problem cannot be predicted in advance because the size of the input array is not known in advance.

Question 10

A recursive solution solves a problem by solving a smaller instance of the same problem.

Accepted Answer

A recursive solution breaks down a problem into smaller sub-problems and solves them in a recursive manner, usually by calling the same function on the smaller sub-problems.

Question 11

A binary search starts at the beginning of the collection of items.

Accepted Answer

A binary search algorithm starts at the middle of the collection of items, not at the beginning. It compares the search key with the middle item in the collection and then decides whether to continue searching in the upper or lower half of the collection.

Question 12

For anArray = <2,3,5,6,9,13,16,19>,what is the value returned by a recursive binary search algorithm if the value being searched for is 10?
A)-1
B)0
C)1
D)10

Accepted Answer

The array is sorted in ascending order and the value being searched (10) falls between 9 and 13. Therefore, the search will move towards the left half of the array, but eventually, the left and right bounds of the narrowed down section will cross each other without finding the value. In this case, the binary search algorithm will return -1 indicating that the value being searched for does not exist in the array.

Question 13

A recursive solution that finds the factorial of n always reduces the problem size by ______ at each recursive call.
A)1
B)2
C)half
D)one-third

Accepted Answer

A recursive solution for finding the factorial of n (n!) typically involves calling the function itself with the argument n-1, thus reducing the problem size by 1 at each step.

Question 14

In the recursive solution to the kth smallest item problem,the problem size decreases by ______ at each recursive call.
A)1
B)at least 1
C)half
D)at least half

Accepted Answer

The problem size decreases by at least 1 at each recursive call because the algorithm eliminates at least one element (the pivot) from consideration in the next step, but the exact number of elements eliminated can vary depending on the pivot's position.

Question 15

A recursive binary search algorithm always reduces the problem size by ______ at each recursive call.
A)1
B)2
C)half
D)one-third

Accepted Answer

In binary search, we divide the search space in half at each recursive call. Therefore, the problem size is reduced by half at each recursive call.

Question 16

A method that is declared as static is an object method.

Accepted Answer

A static method is a method that belongs to the class and not to any instance of the class, therefore it is not an object method. It can be called by using the class name instead of an instance of the class.

Question 17

In a sorted array,the kth smallest item is given by ______.
A)anArray[k-1]
B)anArray[k]
C)anArray[SIZE-k]
D)anArray[SIZE+k]

Accepted Answer

In a sorted array, the smallest item is located at index 0 and the kth item would be located at index k-1. Therefore, the correct option is anArray[k-1].

Question 18

An iterative solution involves loops.

Accepted Answer

This is because an iterative solution typically involves performing a repeated set of instructions or operations on a dataset or problem, often using loops to systematically apply the same logic to each element in the set.

Question 19

For anArray = <2,3,5,6,9,13,16,19>,what is the value returned by a recursive binary search algorithm if the value being searched for is 6?
A)1
B)3
C)4
D)6

Accepted Answer

A recursive binary search algorithm would return the index of the value being searched for in the array. Since arrays are zero-indexed, the value 6 is at index 3 in the given array.

Question 20

Which of the following is a base case for a recursive binary search algorithm? (first is the index of the first item in the array,last is the index of the last item in the array,and mid is the midpoint of the array). A)last > first B)first > last C)0 <= first D)last <= SIZE-1

Accepted Answer

The base case for a recursive binary search algorithm is when the first pointer exceeds the last pointer, meaning that the value is not found in the array. Therefore, the best choice for the base case is B, where first > last.

Quiz 3: Recursion: the Mirrors

A recursive solution can have more than one base cases.

In the recursive solution to the Towers of Hanoi problem,the number of disks to move ______ at each recursive call.

The binary search algorithm can be applied to an unsorted array.

A recursive solution that finds the factorial of n generates ______ recursive calls.

In the Fibonacci sequence,which of the following integers comes after the sequence 1,1,2,3?

An iterative method always calls itself.

Every recursive method must have a base case.

When constructing a recursive solution,you should assume that a recursive call's postcondition is true if its precondition is true.

The base case for a recursive solution to the kth smallest item problem cannot be predicted in advance.

A recursive solution solves a problem by solving a smaller instance of the same problem.

A binary search starts at the beginning of the collection of items.

For anArray = <2,3,5,6,9,13,16,19>,what is the value returned by a recursive binary search algorithm if the value being searched for is 10?

A recursive solution that finds the factorial of n always reduces the problem size by ______ at each recursive call.

In the recursive solution to the kth smallest item problem,the problem size decreases by ______ at each recursive call.

A recursive binary search algorithm always reduces the problem size by ______ at each recursive call.

A method that is declared as static is an object method.

In a sorted array,the kth smallest item is given by ______.

An iterative solution involves loops.

For anArray = <2,3,5,6,9,13,16,19>,what is the value returned by a recursive binary search algorithm if the value being searched for is 6?

Which of the following is a base case for a recursive binary search algorithm? (first is the index of the first item in the array,last is the index of the last item in the array,and mid is the midpoint of the array) .