Deck 11: Recursion

Question 1

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

Answer 1

False

Question 2

All recursive methods must have a/an:
(a)starting case
(b)intermediate case
(c)stopping case
(d)none of the above

Answer 2

C

Question 3

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

Answer 3

D

Question 4

The order of magnitude of the binary search algorithm is:
(a)linear
(b)exponential
(c)logarithmic
(d)quadratic

Question 5

A recursive method is one that:
(a)Returns a value
(b)Initializes a set of variables
(c)Returns no value
(d)Invokes itself

Question 6

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 7

Recursion is:
(a)the ability of a program to call itself
(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 8

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 9

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 10

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 11

The underlying data structure used by the computer during recursion is a:
(a)queue
(b)linked list
(c)tree
(d)stack

Question 12

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 13

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

Question 14

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

Question 15

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 16

A base case must include a recursive call.

Question 17

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 18

All recursive methods have a/an ____________ equivalent method.
(a)Iterative
(b)Selective
(c)Inherited
(d)None of the above

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

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 21

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

Question 22

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

Question 23

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

Question 24

Explain how a sequential search works.

Question 25

Activation records are used to implement recursion.

Question 26

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

Question 27

What is an activation record?

Question 28

Write an iterative method to compute the power of xⁿ for non-negative n.

Question 29

Write a recursive method to compute the power of xⁿ for non-negative n.

Question 30

How does the computer system handle a recursive method call?

Question 31

Explain how the binary search works.

Question 32

What is a base case?

Question 33

Write an iterative method to print a string backwards.

Question 34

Binary search is a divide and conquer algorithm.

Question 35

Write a recursive method to print a string backwards.

Question 36

Explain the concept of divide and conquer.

Question 37

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

Question 38

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

Question 39

A recursive method must never return a value.

Question 40

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

Question 41

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

Question 42

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

Question 43

What is a stack overflow?