Quiz 13: Recursion

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

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

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

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

Every recursive definition can have zero or more base cases.

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

The base case starts the recursion.

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.

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

A method that calls itself is an iterative method.

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

Every recursive call has its own code.

A program will terminate after completing any particular recursive call.

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

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

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

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

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

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

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

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

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

Recursive algorithms are implemented using while loops.

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.

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

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)

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

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

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

What is the output of exampleRecursion(3)? A) 25 C) 36 B) 32 D) 42

What is the output of exampleRecursion(0)? A) 0 C) 9 B) 3 D) 27

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

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)

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

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)

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.

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

What is the output of func2(2, 3)? A) 2 C) 5 B) 3 D) 6

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

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

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

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

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

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

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

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

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.

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

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

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