Deck 11: Recursion

Question 1

All recursive methods have a/an ____________ equivalent method.

A)Iterative
B)Selective
C)Inherited
D)None of the above

Answer 1

A

Question 2

A method definition that includes a call to itself is said to be recursive.

Answer 2

True

Question 3

The portion of memory in which a recursive computation is stored is called a/an:

A)stack frame
B)activation record
C)all of the above
D)none of the above

Answer 3

C

Question 4

A recursive solution can be preferable to an iterative solution because:

A)recursive method calls are faster than iterative looping
B)recursive solutions may be easier to understand than iterative ones
C)recursion uses less memory than iteration
D)iteration should be avoided.

Question 5

Pick the best answer

A)Recursive methods may include a recursive call
B)Recursive methods may not use iteration
C)Recursive methods must include a recursive call
D)none of the above

Question 6

Recursion is:

A)the ability of a program to repeat a block of code
B)the ability of a method to call itself
C)the ability of a method to call smaller methods
D)the ability of a method to implement factorials

Question 7

The stack is a ________________ data structure.

A)first in - first out
B)last in - last out
C)last in - first out
D)none of the above

Question 8

A recursive method is one that:

A)Returns a value
B)Initializes a set of variables
C)Returns no value
D)Invokes itself

Question 9

During recursion,if the stack attempts to grow beyond its limit,a _____________ occurs.

A)Stack underflow
B)Stack overflow
C)Recursive underflow
D)Recursive overflow

Question 10

What is the value returned when the integer 5 is the argument to the factorial method?

A)15
B)50
C)100
D)120

Question 11

When defining recursive void methods you should:

A)Ensure there is no infinite recursion.
B)Ensure that each stopping case performs the correct action for that case.
C)Ensure that if all recursive calls perform their actions correctly,then the entire case performs correctly.
D)All of the above

Question 12

A base case must include a recursive call.

Question 13

The following code for the method factorial)applies to the next two questions: public static double factorial double n)
{
If n == 0)
{
Return 1;
}
Else
{
Return n * factorialn-1);
}
}
What is the value returned when the integer 3 is the argument to the factorial method?

A)2
B)4
C)6
D)8

Question 14

The underlying data structure used by the computer during recursion is a:

A)queue
B)linked list
C)tree
D)stack

Question 15

When a recursive call is encountered,computation is temporarily suspended;all of the information needed to continue the computation is saved and the recursive call is evaluated.

Question 16

Infinite recursion:

A)will happen when there is no base case
B)will not happen when there is a base case
C)will not happen if we use subproblems
D)none of the above

Question 17

When defining recursive valued methods you should:

A)Ensure there is no infinite recursion.
B)Ensure each stopping case returns the correct value for that case.
C)Ensure that the final value returned by the method is the correct value.
D)All of the above

Question 18

The order of magnitude of the binary search algorithm is:

A)linear
B)exponential
C)logarithmic
D)quadratic

Question 19

Regarding recursion,if a base case is never reached the result is:

A)infinite recursion
B)iteration
C)termination
D)all of the above

Question 20

All recursive methods must have a/an:

A)starting case
B)intermediate case
C)stopping case
D)none of the above

Question 21

The binary search algorithm is extremely slow compared to an algorithm that simply tries all array elements in order.

Question 22

What is a base case?

Question 23

Write a recursive method to compute the power of x< sup >n< /sup > for non-negative n.

Question 24

Write a recursive method to compute the factorial of a number.

Question 25

Activation records are used to implement recursion.

Question 26

The binary search algorithm has worst-case running time that is logarithmic.

Question 27

How does the computer system handle a recursive method call?

Question 28

Write an iterative method to compute the power of x< sup >n< /sup > for non-negative n.

Question 29

Explain the concept of divide and conquer.

Question 30

A recursive method must never return a value.

Question 31

Binary search is a divide and conquer algorithm.

Question 32

Explain how a sequential search works.

Question 33

Write a recursive method to print a string backwards.

Question 34

Explain how the binary search works.

Question 35

Write an iterative method to print a string backwards.

Question 36

A recursively written method will usually run slower and use more storage than an equivalent iterative version.

Question 37

A stack is a last-in/first-out memory structure.

Question 38

To keep track of recursion most computer systems us a structure called a queue.

Question 39

What are the criteria you must consider when formulating a recursive solution?

Question 40

Write an iterative method to compute the factorial of a number.

Question 41

What is an activation record?

Question 42

What are two factors that contribute to the inefficiency of some recursive solutions?

Question 43

What are the two base cases for a recursive binary search algorithm?

Question 44

What is a stack overflow?