Deck 8: Recursion

Question 1

A recursive problem-solving strategy has divided a problem of size n into two parts. If the larger problem consists of n - 1 items, the smaller problem consists of __________ item (s).

A) 0
B) 1
C) n - 1
D) n

Answer 1

1

Question 2

Suppose you are recursively searching an array filled with 512 items . If each subdivision returns two smaller arrays with n/2 items, how many smaller arrays are generated at the third level of the search?

A) 2
B) 4
C) 8
D) 16

Answer 2

8

Question 3

A recursive algorithm will stop subdividing a problem after reaching the __________ case.

Answer 3

base

Question 4

The recursive case in the size function below has been incorrectly altered. If the function is called with str = "palindrome", the internal algorithm __________.

A) returns palindrome
B) returns 10
C) returns 1
D) goes into an infinite loop.

Question 5

The altered version of print_chars_reverse defined below will output the characters of the string argument in reverse order.

Question 6

A proof by __________ works the following way:
• Prove the theorem is true for the base case of (usually) n = 0 or n = 1.
• Show that if the theorem is assumed true for n, then it must be true for n + 1.

Question 7

The process of returning from the recursive calls and computing the partial results is called __________ the recursion.

Question 8

C++ maintains a stack, on which it saves new information in the form of a(n) __________ frame.

Question 9

Suppose the function size is called with the argument "ace". When size is later recursively called with the argument "ce", the saved state is represented with the activation frame:
str: "ce"
"ce" == "" is true
return 1 + size("e");

Question 10

Which algorithm segment completes the definition for an iterative version of the factorial function?
Int factorial_i (int n) {
Int result = 1;
/** missing code inserted here */
__________
Return result ;
}

A) if (n == 0)
return 1;
else if (n > 0)
return n * factorial_i(n - 1);
else
B) if (n == 0)
return result;
else if (n > 0)
return n * factorial_i(n - 1);
else
C) for (int i = 1; i <= n; i++)
result *= i;
D) for (int i = 1; i <= n; i++)
n *= i;

Question 11

Complete the revision to the power function below.

Question 12

To complete the recursive call to gcd, which argument set should be inserted?

A) n, m
B) m % n
C) m, n / m
D) n, m % n

Question 13

We can always write an iterative solution to a problem that is solvable by recursion.

Question 14

The iterative and recursive algorithms used to compute a factorial value are O(__________), because the number of loop repetitions or recursive calls increases linearly with n.

A) 1
B) log₂ n
C) n
D) n log₂n

Question 15

The iterative version of a function always requires significantly more memory that a recursive version.

Question 16

Suppose you passed 50 to the naive recursive version of the fibonacci function appearing below.
If your CPU could process one million activation frames per second, approximately how much time would the function require to compute the return value?

A) 36 seconds
B) 36 days
C) 36 years
D) 36 centuries

Question 17

Which of the following recursive calls enables the fibo function to perform in linear time?

A) fibo(fib_current + fib_previous, fib_current, n - 1)
B) fibo(fib_current + fib_previous, fib_current, n - 1) + fibo(fib_current + fib_previous, fib_current, n - 1)
C) fibo(n -1) + fibo (n - 2)
D) fibo(fib_current + fib_previous, fib_current, n )

Question 18

The function below is called a(n) __________ function because its only purpose it to call the recursive fibo function and return its result.
int fibonacci_start(int n) {
return fibo(1, 0, n);
}

Question 19

On average, a linear search will examine __________ items to find the target if it is in the vector.

A) log₂n
B) n/2
C) n
D) n log₂n

Question 20

Binary search must be performed on a(n) __________ array.

Question 21

Rather than examining the last vector element, binary search compares the "__________" element to the target.

Question 22

Because we eliminate at least __________ of the elements from consideration with each recursive call, binary search is an O(log n) algorithm.

A) one-fifth
B) one-quarter
C) one-third
D) one-half

Question 23

When performing a binary search against a vector with 262,144 items, __________ probes are required in the worst case scenario.

Question 24

To test the binary search algorithm, you must test vectors with an even number of elements and vectors with an odd number of elements.

Question 25

__________ is an approach to implementing systematic trial and error in a search for a solution.