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 program will terminate after completing any particular recursive call.

Answer 2

False

Question 3

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

Answer 3

False

Question 4

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

Question 5

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

Question 6

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

Question 7

Every recursive definition can have zero or more base cases.

Question 8

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

Question 9

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

Question 10

Every recursive call has its own code.

Question 11

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

Question 12

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

Question 13

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 14

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

Question 15

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

Question 16

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

Question 17

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

Question 18

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 19

The base case starts the recursion.

Question 20

A method that calls itself is an iterative method.

Question 21

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

Question 22

public static int func2(int m, int n)
{
If (n == 0)
Return 0;
Else
Return m + func2(m, n - 1);
}What is the output of func2(2, 3)?

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

Question 23

public static int func1(int m, int n)
{
If (m == n || n == 1)
Return 1;
Else
Return func1(m - 1, n - 1) + n * func1(m - 1, n);
}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)
B) func1(1, 1)
C) func1(1, 2)
D) func1(2, 0)

Question 24

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

Question 25

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 26

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}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 27

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}How many base cases are in the code in the accompanying figure?

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

Question 28

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What is the output of exampleRecursion(3)?

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

Question 29

public static int func2(int m, int n)
{
If (n == 0)
Return 0;
Else
Return m + func2(m, n - 1);
}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 30

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
B) 72
C) 720
D) None of these

Question 31

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}Which of the following is an invalid call to the method in the accompanying figure?

A) exampleRecursion(-1)
B) exampleRecursion( 0)
C) exampleRecursion(1)
D) exampleRecursion(999)

Question 32

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What is the output of exampleRecursion(0)?

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

Question 33

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 34

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

Question 35

public static int func2(int m, int n)
{
If (n == 0)
Return 0;
Else
Return m + func2(m, n - 1);
}What is the limiting condition of the code in the accompanying figure?

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

Question 36

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)
B) Only (ii)
C) Only (iii)
D) Both (i) and (iii)

Question 37

Recursive algorithms are implemented using while loops.

Question 38

public static int exampleRecursion (int n)
{
If (n == 0)
Return 0;
Else
Return exampleRecursion(n - 1) + n * n * n;
}What is the limiting condition of the code in the accompanying figure?

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

Question 39

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
B) Statements in Lines 5 and 6
C) Statements in Lines 3, 4, and 5
D) None of these

Question 40

public static int func1(int m, int n)
{
If (m == n || n == 1)
Return 1;
Else
Return func1(m - 1, n - 1) + n * func1(m - 1, n);
}What precondition must exist in order to prevent the code in the accompanying figure from infinite recursion?

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

Question 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
B) B
C) C
D) D

Question 42

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 declarationint[] alpha = {1, 4, 5, 8, 9};What is the output of the following statement?System.out.println(mystery(alpha, 0, 4));

A) 1
B) 18
C) 27
D) 32

Question 43

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

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

Question 44

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 45

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 declarationint[] 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
B) 33
C) 55
D) 66

Question 46

____ is NOT an iterative control structure.

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

Question 47

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 48

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 49

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
B) 400
C) 500
D) 10,000

Question 50

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