Deck 6: Recursion

Question 1

Recursion is a very powerful way to solve certain problems for which the solution would otherwise be very complicated.

Answer 1

True

Question 2

The recursive algorithm must have three or more base cases.

Answer 2

False

Question 3

A function that calls itself is an iterative function.

Answer 3

False

Question 4

The base case starts the recursion in a recursive function.

Question 5

Logically, you can think of a recursive function as having an unlimited number of copies of itself.

Question 6

In recursion, the execution in the previous call begins from the point immediately following the recursive call.

Question 7

After completing a particular recursive call, the program terminates.

Question 8

Indirect recursion requires the same careful analysis as direct recursion.

Question 9

Tracing through indirect recursion can be tedious.

Question 10

The base case is never reached or does not exist in an infinite recursion.

Question 11

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

Question 12

Certain applications might require the data in an ordered list to be printed in descending order, which means that we must print the list backward.

Question 13

We can traverse a singly linked list backward starting from the last node.

Question 14

The execution of the recursive version of the program to calculate a Fibonacci number is as efficient as the execution of the nonrecursive version.

Question 15

The rightmost bit of 33 is 2.

Question 16

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

A) iteration
B) succession
C) recursion
D) repulsion

Question 17

An algorithm that finds the solution to a given problem by reducing the problem to smaller versions of itself is called a(n) ____.

A) iterative algorithm
B) recursive algorithm
C) regressive algorithm
D) successive algorithm

Question 18

A function is called ____ recursive if it calls itself.

A) indirectly
B) implicitly
C) apparently
D) directly

Question 19

A function that calls another function and eventually results in the original function call is said to be ____ recursive.

A) directly
B) indeterminantly
C) indirectly
D) suspiciously

Question 20

Every call to a recursive function has its own code and its own set of ____ and local variables.

A) headers
B) parameters
C) stack
D) heap

Question 21

The nodes of an ordered linked list are in ____ order.

A) descending
B) optimized
C) unknown
D) ascending

Question 22

Given a pointer to a list, the function ____ prints the elements of the list in reverse order.

A) reverse
B) reversePrint
C) invert
D) translate

Question 23

A sequence of number such as 1, 1, 2, 3, 5, 8, 13, 21, 34, ... is called a ____ sequence.

A) Newtonian
B) Gaussian
C) Fibonacci
D) Marconi

Question 24

In the Tower of Hanoi problem, it would take about ____ years for the computer to generate 2⁶⁴ moves at the rate of 1 billion moves per second.

A) 5
B) 50
C) 500
D) 5,000

Question 25

We call the remainder of x after division by 2 the ____ bit of x.

A) rightmost
B) leftmost
C) middlemost
D) innermost

Question 26

____ use a looping structure, such as while, for, or do. . .while, to repeat a set of statements.

A) Recursive control structures
B) Iterative control structures
C) Sequential control structures
D) Decisions structures

Question 27

In addition to the nature of the solution, ____ is the other key factor in determining whether recursion or iteration is the better approach.

A) latitude
B) elegance
C) efficacy
D) efficiency

Question 28

When a function is called, ____ is allocated for its formal parameters and local variables.

A) nothing
B) memory space
C) global space
D) heap space

Question 29

When the function terminates, its memory space is ____.

A) allocated
B) recycled
C) left intact
D) deallocated

Question 30

Every recursive call requires the system to allocate memory space for its ____ and local variables.

A) formal parameters
B) informal parameters
C) global values
D) register values

Question 31

Even though we don't need to write program statements to allocate and deallocate memory, ____ is associated with executing a recursive function, both in terms of memory space and execution time.

A) overburden
B) compiler interpretation
C) overhead
D) code interpretation

Question 32

A recursive function executes ____ its iterative counterpart.

A) more slowly than
B) more quickly than
C) at the same speed as
D) proportionately to

Question 33

A recursive function is ____ a corresponding iterative function in terms of execution time and memory usage.

A) more efficient than
B) proportional to
C) similar to
D) less efficient than

Question 34

The ____ attempts to find solutions to a problem by constructing partial solutions and making sure that any partial solution does not violate the problem requirements.

A) backtracking algorithm
B) inferring algorithm
C) interpretation algorithm
D) stack tracing algorithm

Question 35

The ____ algorithm tries to extend a partial solution toward completion.

A) backordering
B) tracing
C) backtracking
D) recursive

Question 36

The solutions generated by the backtracking algorithm can be best represented by a(n) ____.

A) list
B) record
C) tree
D) array