Deck 13: Recursion

Question 1

The factorial method returns the factorial of n as a(n):

A) void.
B) float.
C) int.
D) String.

Answer 1

C

Question 2

An iterative function is implemented with looping constructs (e.g., while or for statements) and repeatedly executes the loop.

Answer 2

True

Question 3

The factorial of 6 is __________.

Answer 3

720

Question 4

Provide the missing code in line 19 of this code segment.
15 if ( dividend % divisor == 0 ) // base case
16 {
17 System.out.println( "\nbase case reached, returning "
18 + divisor + "\n" );
19 // Insert missing code here
20 }
21 else // general case

Question 5

You are using a binary search algorithm to search a sorted array for a given value. Organize the steps in defining bases cases and the general case by listing the order in which they should occur.
1) Assuming that the array is not empty, formulate the general case to search both higher and lower for the value, making a recursive call to our search method.
2) Define the base case such that if the value of the middle element is the value we seek, it will return its index.
3) Return -1 when the array is empty (i.e., a base case is reached).
4) Continue searching; the part of the array being searched will shrink until it is empty.

Question 6

Why might you want to use a recursive method instead of a loop?

A) The code is more compact.
B) The code is more elegant.
C) The code is simpler.
D) All of these are correct.

Question 7

The formula that reduces the size of the problem is called the general case.

Question 8

In the body of a __________ method, there is a call to the method itself.

A) base case
B) general case
C) recursion
D) recursive

Question 9

Recursive methods can be defined as static or nonstatic.

Question 10

What is gcd?

A) The greatest common determiner
B) The greatest positive integer that divides evenly into two positive integers
C) The method that finds the factors of two positive integers
D) All of these are correct.

Question 11

Each execution of the recursive method must wait to return its value until its recursive call to the method returns a value.

Question 12

What will happen if you code for only one base case when there are two or more base cases?

A) The missing base cases will never be detected.
B) The recursive calls will continue to be made.
C) The program will generate a StackOverflowError.
D) All of these are correct.

Question 13

If there are two recursive terms on the right side of the formula, there will be one base case.

Question 14

When searching for a value in an array, what are the possible outcomes?

A) We find the value and return its array index.
B) We do not find the value and return -1.
C) We find the value and return its array index or we do not find the value and return -1.
D) None of these is correct.

Question 15

In solving the Towers of Hanoi problem, when the if statement identifies the base case, it allows the program to keep moving disks until there are no more disks to move.

Question 16

A recursive function is implemented using decision constructs, while an iterative function is implemented with looping constructs.

Question 17

A binary search is more easily coded using iteration rather than recursion.

Question 18

In the body of a recursive method, there is a call to the:

A) base case.
B) general case.
C) method.
D) class.

Question 19

Recursion allows us to do which of the following?

A) We can solve a large problem by reducing it to smaller problems until we find a problem that we can solve.
B) We can redefine classes for reuse.
C) We can define large problems for experts to solve.
D) All of these are correct.

Question 20

Which of the following defines the general case?

A) if (n > 0 )
B) public static void main( String [n > 0] )
C) else // n = 0
D) public base case void (n > 0)

Question 21

Which code would you use to trace recursive calls, where the desired expression goes inside the parentheses?

A) System.out.println ( )
B) System.print.trace ( )
C) System.traceprint ( )
D) if System.out ( )

Question 22

The efficiency of the method at execution time is called the:

A) array time.
B) if/else report.
C) running time.
D) status.

Question 23

With a tail recursive method, the ___________ stays the same.

A) return value
B) recursive call
C) parameter value
D) modulus operation

Question 24

Why is recursion often slower than iteration?

A) Although the coding is elegant, implementation takes longer.
B) There is overhead associated with recursive method calls.
C) Running times are of the same order of magnitude.
D) The general case can be more difficult to solve.

Question 25

The idea of __________ is to reduce the size of a problem at each step so that we eventually arrive at a very small, easy-to-solve problem.

A) recursion
B) iteration
C) reduction
D) generalization

Question 26

Failure to code the base case will result in a runtime error.

Question 27

A base case must have the words "base case" in order to be coded correctly.

Question 28

A factorial method is complete when it generates:

A) a recursive call to the factorial method with the argument 0.
B) an indefinite method.
C) a recursive call to the factorial method with the argument -1.
D) None of these is correct.

Question 29

When a method is called, the JVM stores the method's arguments and the caller's return address on a(n):

A) overflow.
B) factorial.
C) tower.
D) None of these is correct.

Question 30

When the recursive calls all the way to the base case and the return value stays the same throughout the process, the method is called:

A) stack overflow.
B) tail recursive.
C) uniform recursive.
D) None of these is correct.

Question 31

What would be a good first base case if you were determining whether a String is a palindrome?

A) If the String is the empty String or contains only 1 character, it is a palindrome.
B) The method calls itself indefinitely until it finds a palindrome.
C) The String calls the first character and then terminates.
D) There is only one character left.

Question 32

If your method implementation does not animate or animates incorrectly, which of the following should you do?

A) Verify that you coded the base cases correctly.
B) Verify that you coded the tail recursive correctly.
C) Check the feedback on the input to see if the code gives the correct result.
D) All of these are correct.

Question 33

You are considering running a program similar to the Tower of Hanoi. Which of the following is true?

A) Iteration would probably be more elegant.
B) Recursion would probably be easier to understand.
C) Recursion would probably have a faster run time.
D) Iteration would probably be easier to implement.

Question 34

Which of the following are reasons to choose recursion over iteration?

A) Run times are equivalent.
B) Recursion implementation is easier to understand.
C) The equivalent iteration implementation would be harder to understand.
D) All of these are correct.

Question 35

Binary search (recursive or iterative) applies to:

A) a sorted array.
B) an unsorted array.
C) either an unsorted or a sorted array.

Question 36

In the body of a recursive method, there is a call to the method itself.

Question 37

In a value-returning method, the return statement can include a call to another value-returning method.

Question 38

The factorial of 5 is 120.

Question 39

Typically, recursion uses selection and iteration uses looping.

Question 40

It is possible that a method does nothing in the base case.

Question 41

A recursive method can be a value-returning method.

Question 42

Usually, not coding the base case will result in a runtime exception caused by the infinite number of recursive calls.

Question 43

Using recursion, the size of a problem is always reduced by 1 (i.e., from n to n − 1).

Question 44

The idea of recursion is to __________ the size of the problem at each step so that we eventually reach an easy-to-solve problem.

Question 45

The easy-to-solve problem resulting from recursion is called the __________ case.

Question 46

Solve the factorial of 4. Show your work.

Question 47

Justify writing pseudocode before writing the Java code.

Question 48

Lynn is having a dinner party for six people. She wrote a factorial program to find out how many possible seating arrangements she has available, but she was stunned when the result was 720. That is too many options. How could she improve her program so that she can find a number of possibilities that she could work with? If she finds that number, how could she incorporate it in her seating decisions?

Question 49

List three features that make using an iteration preferable to a recursion in printing "Happy Birthday" 10 times.

Question 50

Why would you probably not want to write a program to find the even numbers from 1 to 20?

Question 51

Evaluate why a recursion method is useful for calculating the greatest common divisor.

Question 52

Using the gcd method, Aidan coded a program to find the common divisor for 43,822 and 52,003. Instead, he got a StackOverflowError. Infer what happened.

Question 53

Identify what must be changed to make this a true statement: To search a sorted array for a given value, you must define a base case to reduce the size of the problem and general cases to implement the base case.

Question 54

Identify the two things you must define in order to construct a recursive solution to a problem.

Question 55

What is the factorial of -12?

Question 56

A Euclidian algorithm finds the gcd of two positive integers a and b. If the two parameters of the method are dividend and divisor, identify when you will have reached the base case.

Question 57

Write a recursive formula in which the following conditions apply:
In the first term, both method parameters, n and p, have each been decreased by 1.
In the second term, n is unchanged, while p is decreased by 1.

Question 58

In this chapter, source files are provided to complete programming activities. Theorize why these files are provided.

Question 59

Would you recommend using recursion or iteration in setting up a program for moving pallets of cargo off a ship? Justify your answer.