# Quiz 13: Recursion

Computing

Q 1Q 1

The process of solving a problem by reducing it to smaller versions of itself is called recursion.

Free

True False

True

Q 2Q 2

In the base case of a recursive solution, the solution is obtained through a call to a smaller version of the original method.

Free

True False

False

Q 3Q 3

The general case of a recursive solution is the case for which the solution is obtained directly.

Free

True False

False

Q 4Q 4

The following is a valid recursive definition to determine the factorial of a non-negative integer. 0! = 1 1! = 1 n! = n * (n - 1)! if n > 0

Free

True False

Free

True False

Free

True False

Free

True False

Q 8Q 8

The following is an example of a recursive method. public static int recFunc(int x) {return (nextNum(nextNum(x)));} where nextNum is method such that nextNum(x) = x + 1.

Free

True False

Q 9Q 9

The body of a recursive method contains a statement that causes the same method to execute before completing the current call.

Free

True False

Free

True False

Free

True False

Free

True False

Free

True False

Free

True False

Q 15Q 15

A method that calls another method and eventually results in the original method call is called indirectly recursive.

Free

True False

Q 16Q 16

If every recursive call results in another recursive call, then the recursive method (algorithm) is said to have infinite recursion.

Free

True False

Q 17Q 17

In reality, if you execute an infinite recursive method on a computer, it will execute forever.

Free

True False

Q 18Q 18

A recursive method in which the first statement executed is a recursive call is called a tail recursive method.

Free

True False

Q 19Q 19

The recursive implementation of the factorial method is an example of a tail recursive method.

Free

True False

Free

True False

Q 21Q 21

The limiting condition for a recursive method using a list might be the number of elements in the list.

Free

True False

Q 22Q 22

There are two base cases in the recursive implementation of generating a Fibonacci sequence.

Free

True False

Free

True False

Q 24Q 24

The overhead associated with iterative methods is greater in terms of both memory space and computer time compared to the overhead associated with executing recursive methods.

Free

True False

Free

True False

Q 26Q 26

Which of the following statements describe the base case of a recursive algorithm? (i) F(0) = 0; (ii) F(x) = 2 * F(x - 1); (iii) if (x == 0) F(x) = 5 + x;
A) Only (i)
C) Only (iii)
B) Only (ii)
D) Both (i) and (iii)

Free

Multiple Choice

Q 27Q 27

Consider the following definition of a recursive method. public static int foo(int n) //Line 1 { //Line 2 if (n == 0) //Line 3 return 0; //Line 4 else //Line 5 return n + foo(n - 1); //Line 6} Which of the statements represent the base case?
A) Statements in Lines 3 and 4
C) Statements in Lines 3, 4, and 5
B) Statements in Lines 5 and 6
D) None of these

Free

Multiple Choice

Q 28Q 28

What does the code in the accompanying figure do?
A) Returns the cube of the number n
B) Returns the sum of the cubes of the numbers, 0 to n
C) Returns three times the number n
D) Returns the next number in a Fibonacci sequence

Free

Multiple Choice

Q 29Q 29

How many base cases are in the code in the accompanying figure?
A) zero
C) two
B) one
D) three

Free

Multiple Choice

Free

Multiple Choice

Free

Multiple Choice

Q 32Q 32

What is the limiting condition of the code in the accompanying figure?
A) n >= 0
C) n > 1
B) n > 0
D) n >= 1

Free

Multiple Choice

Q 33Q 33

Which of the following is an invalid call to the method in the accompanying figure?
A) exampleRecursion(-1)
C) exampleRecursion(1)
B) exampleRecursion( 0)
D) exampleRecursion(999)

Free

Multiple Choice

Q 34Q 34

What precondition must exist in order to prevent the code in the accompanying figure from infinite recursion?
A) m >= 0 and n >= 0
C) m >= 1 and n >= 0
B) m >= 0 and n >= 1
D) m >= 1 and n >= 1

Free

Multiple Choice

Q 35Q 35

Given the code in the accompanying figure, which of the following method calls would result in the value 1 being returned?
A) func1(1, 0)
C) func1(1, 2)
B) func1(1, 1)
D) func1(2, 0)

Free

Multiple Choice

Q 36Q 36

Which of the following statements is NOT true about infinite recursion?
A) In theory, infinite recursion executes forever.
B) In reality, infinite recursion will lead to a computer running out of memory and abnormal termination of the program.
C) Methods that are indirectly recursive always lead to infinite recursion.
D) If recursive calls never lead to a base case, infinite recursion occurs.

Free

Multiple Choice

Q 37Q 37

What is the limiting condition of the code in the accompanying figure?
A) n >= 0
C) m >= 0
B) m > n
D) n > m

Free

Multiple Choice

Free

Multiple Choice

Q 39Q 39

Which of the following statements about the code in the accompanying is always true?
A) func2(m, n) = func2(n, m) for m >= 0
B) func2(m, n) = m * n for n >= 0
C) func2(m, n) = m + n for n >= 0
D) func2(m, n) = n * m for m >= 0

Free

Multiple Choice

Q 40Q 40

Consider the following definition of a recursive method. public static int recFunc(int num) {if (num >= 10) return 10; else return num * recFunc(num + 1);} What is the output of the following statement? System.out.println(recFunc(8));
A) 8
C) 720
B) 72
D) None of these

Free

Multiple Choice

Q 41Q 41

Assume there are four methods A, B, C, and D. If method A calls method B, method B calls method C, method C calls method D, and method D calls method A, which of the following methods is indirectly recursive?
A) A
C) C
B) B
D) D

Free

Multiple Choice

Q 42Q 42

Consider the following definition of a recursive method. public static int recFunc(int num) {if (num >= 10) return 10; else return num * recFunc(num + 1);} What is the output of the following statement? System.out.println(recFunc(10));
A) 10
B) 110
C) This statement results in infinite recursion.
D) None of these

Free

Multiple Choice

Q 43Q 43

Consider the following definition of a recursive method. public static int mystery(int[] list, int first, int last) {if (first == last) return list[first]; else return list[first] + mystery(list, first + 1, last);} Given the declaration int[] alpha = {1, 4, 5, 8, 9}; What is the output of the following statement? System.out.println(mystery(alpha, 0, 4));
A) 1
C) 27
B) 18
D) 32

Free

Multiple Choice

Q 44Q 44

Consider the following definition of a recursive method. public static int strange(int[] list, int first, int last) {if (first == last) return list[first]; else return list[first] + strange(list, first + 1, last);} Given the declaration int[] beta = {2, 5, 8, 9, 13, 15, 18, 20, 23, 25}; What is the output of the following statement? System.out.println(strange(beta, 4, 7));
A) 27
C) 55
B) 33
D) 66

Free

Multiple Choice

Q 45Q 45

The third Fibonacci number is ____.
A) the sum of the first two Fibonacci numbers
B) the sum of the last two Fibonacci numbers
C) the product of the first two Fibonacci numbers
D) the product of the last two Fibonacci numbers

Free

Multiple Choice

Q 46Q 46

In the recursive algorithm for the nth Fibonacci number, there are ____ base case(s).
A) zero
C) two
B) one
D) three

Free

Multiple Choice

Q 47Q 47

What is the first step in the Tower of Hanoi recursive algorithm?
A) Move the top n disks from needle 1 to needle 2, using needle 3 as the intermediate needle.
B) Move disk number n from needle 1 to needle 3.
C) Move the top n - 1 disks from needle 2 to needle 3, using needle 1 as the intermediate needle.
D) Move the top n - 1 disks from needle 1 to needle 2, using needle 3 as the intermediate needle.

Free

Multiple Choice

Q 48Q 48

Using a recursive algorithm to solve the Tower of Hanoi problem, a computer that can generate one billion moves per second would take ____ years to solve the problem.
A) 39
C) 500
B) 400
D) 10,000

Free

Multiple Choice

Q 49Q 49

____ is NOT an iterative control structure.
A) A while loop
C) Recursion
B) A for loop
D) A do...while loop

Free

Multiple Choice

Q 50Q 50

If you are building a mission control system, ____.
A) you should always use iteration
B) you should always use recursion
C) use the most efficient solution
D) use the solution that makes the most intuitive sense

Free

Multiple Choice