Deck 11: Recursion

Question 1

A good way to think about recursion is a function that calls itself.

Answer 1

False

Question 2

There can be any number of function execution instances of a given recursive function.

Answer 2

True

Question 3

Every properly designed recursive function must conditionally call another execution instance of itself.

Answer 3

True

Question 4

Every time a call a recursive function call is made, the same execution instance is executed.

Question 5

Every time a call a recursive function call is made, the same execution instance is executed.

Question 6

A recursive function is a good choice, in practice, for implementation of the factorial function.

Question 7

Recursive functions may have more than one bast case.

Question 8

A recursive function is a

A) a function definition that refers to itself, and execution instances calling other execution instances of the same function definition.
B) a function definition that refers to itself, and execution instances calling themselves.
C) a function definition that refers to another function definition, and execution instances calling other function instances of the same function.
D) a function definition that refers to another function definition, and execution instances calling themselves.

Question 9

The advantage of the use of recursion is that

A) recursive functions execute very quickly
B) recursion functions are memory efficient
C) recursion functions are execution time efficient
D) recursion functions are execution time efficient.
E) it is a powerful problem-solving approach

Question 10

An improperly designed recursive function may result in a nonterminating sequences of execution instances. This is referred to as ________________________.

Question 11

Three important characteristics of any recursive function are that there must be at least one base case,problems that are not a base case are broken down into subproblems that are a similar kind of problem as the original problem and work towards the base case, and ______________.

Question 12

Describe the series of recursive function calls for computing the factorial of 3.

Question 13

Give a Python recursive function definition for the factorial function.

Question 14

Describe, in terms of n, what the following recursive function computes.

Question 15

Describe the output of the following recursive function.
def rfunc(n):
if n == 0:
print('*', end='')
return
else:
print('-', end='')
rfunc(n - 1)
print('-', end='')

Question 16

In recursive problem solving, a problem is broken down into subproblems in which each subproblem must be the same kind of problem as the original.

Question 17

In recursive problem solving, it is often most effective to break the problem down into equal size subproblems.

Question 18

MergeSort is a clever, but inefficient, means of recursive problem solving.

Question 19

The base case in MergeSort is when a sublist is found to be completely sorted.

Question 20

A recursive function definition may only call itself once from within the definition.

Question 21

What is the total number of calls to recursive function MergeSort that are made to sort a list of 8 elements?

Question 22

For the list 10, 7, 3, 12, 18, 20, 4, 15, what will be the ordering of the elements immediately after the first merging of elements occurs?

Question 23

For the list 6, 11, 21, 32, 5, 14, 9, 19, what will be the ordering of the elements just before the last merging of elements occurs?

Question 24

What would need to be changed in the MergeSort algorithm (as given in the textbook) so that lists were sorted in descending, rather than ascending order?

Question 25

Whatever can be computed using recursion can be accomplished by the use of iteration.

Question 26

When a problem can be solved both recursively and iteratively with similar programming effort, it is generally best to use an iterative approach.

Question 27

Any problem that can be easily solved with the use of recursion can also be easily solved using iteration.