Deck 14: Recursion

Question 1

When a function A calls a function B, which in turn calls A, we have

A) direct recursion.
B) indirect recursion.
C) function call cycling.
D) perfect recursion.
E) None of the above

Answer 1

B

Question 2

The quicksort algorithm can be used to

A) sort lists stored in arrays.
B) perform binary search on arrays.
C) quickly sort and search arrays.
D) All of the above
E) None of the above

Answer 2

A

Question 3

A recursive function should be designed to stop making recursive calls when it reaches its

A) return statement.
B) base case.
C) closing curly brace.
D) last parameter.
E) None of the above

Answer 3

B

Question 4

A ________ function is one that calls itself.

A) dynamic
B) static
C) recursive
D) data validation
E) None of the above

Question 5

Any algorithm that can be coded with recursion can also be coded using a loop.

Question 6

The function int fact(int k)
{
Return k*fact(k-1);
If (k==0) return 1;
}

A) computes the factorial on an integer k passed to it as parameter.
B) returns the value 1 if it is passed a value of 0 for the parameter k.
C) does not correctly handle its base case.
D) works for all non-negative values of k, but not for negative numbers.
E) None of the above

Question 7

The base case of a recursive function

A) is 0.
B) is 1.
C) is depth / 2.
D) is 1 / (depth * 3.1415).
E) depends on the problem being solved.

Question 8

The ________ of recursion is the number of times a recursive function calls itself.

A) level
B) breadth
C) type
D) depth
E) None of the above

Question 9

Recursion can be used to

A) compute factorials.
B) find the greatest common divisor of two integers (GCD).
D) All of the above
C) program things that cannot be programmed without recursion.

Question 10

The QuickSort algorithm was developed in 1960 by

A) Bjarne Stroustrup.
B) Tony Gaddis.
C) C.A.R. Hoare.
D) Judy Walters.
E) None of the above

Question 11

The speed and amount of memory available to modern computers diminishes the performance impact of the overhead of recursion so much that for many applications, this overhead is not noticeable.

Question 12

Suppose that a recursive function with integer parameter n has a base case of 0, and for each non-base case, the function makes a recursive call with argument n+1. If the function is initially called with an actual argument of n = 3, the function call will

A) cause an infinite chain of recursive calls.
B) return after a chain of 2 recursive calls.
C) return after a chain of 3 recursive calls.
D) return after a chain of 4 recursive calls.
E) None of the above

Question 13

The ________ algorithm uses recursion to sort an array.

A) shell sort
B) quicksort
C) binary sort
D) red/black sort
E) None of the above

Question 14

Indirect recursion means that a function calls itself several times.

Question 15

A recursive function cannot call a function other than itself.

Question 16

The quicksort algorithm works on the basis of

A) three sublists.
B) two sublists and a pivot.
C) two pivots and a sublist.
D) three pivots.
E) None of the above

Question 17

Recursive algorithms tend to be less efficient than iterative algorithms.

Question 18

A recursive function that does not correctly handle its base case may

A) return 0 and stop.
B) return FALSE and stop.
C) cause an infinite chain of recursive calls.
D) reach the NULL terminator and stop.
E) None of the above

Question 19

When a recursive function directly calls itself, this is known as direct recursion.

Question 20

The programmer must ensure that a recursive function does not become

A) a static function.
B) a prototyped function.
C) trapped in an infinite chain of recursive calls.
D) a dynamic function.
E) None of the above