Deck 13: Recursion

Question 1

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

Answer 1

True

Question 2

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

Answer 2

False

Question 3

A program will terminate after completing any particular recursive call.

Answer 3

False

Question 4

The base case starts the recursion.

Question 5

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

Question 6

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

Question 7

You can think of a recursive method as having unlimited copies of itself.

Question 8

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

Question 9

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

Question 10

To design a recursive method, you must determine the limiting conditions.

Question 11

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

Question 12

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.

Question 13

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

Question 14

Every recursive call has its own code.

Question 15

A method that calls itself is an iterative method.

Question 16

Every recursive definition can have zero or more base cases.

Question 17

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

Question 18

A method is called directly recursive if it calls another recursive method.

Question 19

A general case to a recursive algorithm must eventually reduce to a base case.

Question 20

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

Question 21

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.

Question 22

A recursive solution is always a better alternative to an iterative solution.

Question 23

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)

Question 24

What is the output of exampleRecursion(3)?

A) 25
C) 36
B) 32
D) 42

Question 25

What is the output of exampleRecursion(0)?

A) 0
C) 9
B) 3
D) 27

Question 26

Recursive algorithms are implemented using while loops.

Question 27

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)

Question 28

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

Question 29

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

Question 30

What is the limiting condition of the code in the accompanying figure?

A) n >= 0
C) m >= 0
B) m > n
D) n > m

Question 31

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

Question 32

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

Question 33

How many base cases are in the code in the accompanying figure?

A) zero
C) two
B) one
D) three

Question 34

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)

Question 35

What is the limiting condition of the code in the accompanying figure?

A) n >= 0
C) n > 1
B) n > 0
D) n >= 1

Question 36

What is the output of func2(2, 3)?

A) 2
C) 5
B) 3
D) 6

Question 37

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

Question 38

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.

Question 39

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

Question 40

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

Question 41

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

Question 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

Question 43

In the recursive algorithm for the nth Fibonacci number, there are ____ base case(s).

A) zero
C) two
B) one
D) three

Question 44

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.

Question 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

Question 46

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

Question 47

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

Question 48

____ is NOT an iterative control structure.

A) A while loop
C) Recursion
B) A for loop
D) A do...while loop

Question 49

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

Question 50

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