Chapter 15

Question 1

True or false:
The following is a valid recursive definition to determine the factorial of a non-negative integer.
0! = 1
1! = 1
n! = n * (n - 1)! if n > 0

Answer 1

True

Question 2

True or false:
In a recursive function, the base case stops the recursion.

Answer 2

False

Question 3

True or false:
With recursion, the base case must eventually be reduced to a general case.

Answer 3

False

Question 4

True or false:
The following is an example of a recursive function.
void print(int x)
{
if (x > 0)
{
cout &laquo_space;x &laquo_space;” “ ;
print (x - 1);
}
}

Answer 4

True

Question 5

True or false:
Every call to a recursive function requires the system to allocate memory for the local variables and formal parameters

Answer 5

True

Question 6

True or false:
Infinite recursions execute forever on a computer.

Answer 6

False

Question 7

True or false:
ou can use a recursive algorithm to find the largest element in an array.

Answer 7

True

Question 8

True or false:
To design a recursive function, you must determine the limiting conditions.

Answer 8

True

Question 9

A definition in which something is defined in terms of a smaller version of itself is called a(n) ____ definition.

Answer 9

recursive

Question 10

The ____ case is the case for which the solution to an equation is obtained directly.

Answer 10

base

Question 11

int foo(int n)
{
if (n == 0)
return 0;
else
return n + foo(n - 1);
}
Consider the accompanying definition of a recursive function. Which of the statements represents the base case?

Answer 11

Statements in lines 3 and 4

Question 12

int foo(int n)
{
if (n == 0)
return 0;
else
return n + foo(n - 1);
}
Consider the accompanying definition of a recursive function. Which of the statements represents the general case?

Answer 12

Statements in lines 5 and 6

Question 13

void printNum(int num)
{
if (n < 0)
cout &laquo_space;“Num is negative” &laquo_space;
endl;
else if (num == 0)
cout &laquo_space;“Num is zero” &laquo_space;endl;
else
{
cout &laquo_space;num &laquo_space;” “;
printNum(num – 1);
}
}
Consider the accompanying definition of a recursive function. Which of the statements represent the base case?

Answer 13

Statements in lines 3-6

Question 14

void printNum(int num)
{
if (n < 0)
cout &laquo_space;“Num is negative” &laquo_space;
endl;
else if (num == 0)
cout &laquo_space;“Num is zero” &laquo_space;endl;
else
{
cout &laquo_space;num &laquo_space;” “;
printNum(num – 1);
}
}
Consider the accompanying definition of a recursive function. Which of the statements represent the general case?

Answer 14

Statements in lines 7-11

Question 15

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
Consider the accompanying definition of a recursive function. What is the output of the following statement?
cout &laquo_space;recFunc(8) &laquo_space;endl;

Answer 15

720

Question 16

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
Consider the accompanying definition of a recursive function. What is the output of the following statement?
cout &laquo_space;recFunc(10) &laquo_space;endl;

Answer 16

10

Question 17

Consider the following definition of the recursive function print.
void print(int num)
{
if (num > 0)
{
cout &laquo_space;num &laquo_space;” “;
print(num - 1);
}
}
What is the output of the following statement?
print(4);

Answer 17

4 3 2 1

Question 18

Tracing through ____ recursion is more tedious than tracing other recursive forms

Answer 18

indirect

Question 19

A function is called ____ if it calls itself.

Answer 19

directly recursive

Question 20

A recursive function in which the last statement executed is the recursive call is called a(n) ____ recursive function.

Answer 20

tail

Question 21

f every recursive call results in another recursive call, then the recursive function (algorithm) is said to have ____
recursion.

Answer 21

infinite

Question 22

int mystery(int list[], int first, int last)
{
if (first == last)
return list[first];
else
return list[first] + mystery(list, first + 1, last);
}
Consider the accompanying definition of the recursive function mystery. Given the declaration:
int alpha[5] = {1, 4, 5, 8, 9};
what is the output of the following statement?
cout &laquo_space;mystery(alpha, 0, 4) &laquo_space;endl;

Answer 22

27

Question 23

Consider the following definition of the recursive function mystery.
int mystery(int first, int last)
{
if (first > last)
return 0;
else if (first == last)
return first;
else
return first + mystery(first + 1, last - 1);
}
What is the output of the following statement?
cout &laquo_space;mystery(6, 10) &laquo_space;endl;

Answer 23

21

Question 24

Consider the following definition of the recursive function mystery.
int mystery(int num)
{
if (num <= 0)
return 0;
else if (num % 2 == 0)
return num + mystery(num – 1);
else
return num * mystery(num – 1);
}
What is the output of the following statement?
cout &laquo_space;mystery(5) &laquo_space;endl;

Answer 24

50

Question 25

int puzzle(int start, int end)
{
if (start > end)
return start - end;
else if (start == end)
return start + end;
else
return end * puzzle(start + 1, end - 1);
}
Consider the accompanying definition of a recursive function. What is the output of the following statement?
cout &laquo_space;puzzle(5, 10) &laquo_space;endl;

Answer 25

720

Question 26

int puzzle(int start, int end)
{
if (start > end)
return start - end;
else if (start == end)
return start + end;
else
return end * puzzle(start + 1, end - 1);
}
Consider the accompanying definition of a recursive function. What is the output of the following statement?
cout &laquo_space;puzzle(3, 7) &laquo_space;endl;

Answer 26

42

Question 27

Which of the following function headings can be used for a recursive definition of a function to calculate the nth
Fibonacci number?

Answer 27

int rFibNum(int a, int b, int n)

Question 28

How many needles are used in the Tower of Hanoi problem?

Answer 28

three

Question 29

Which of the following rules should you follow to solve the Tower of Hanoi problem?

Answer 29

A smaller disk can be placed on top of a larger disk.

Question 30

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

Answer 30

iterative

Question 31

Which of the following solution methods would be the best choice for a mission control system?

Answer 31

recursive

Question 32

Which of the following solutions is easier to construct for the Tower of Hanoi problem?

Answer 32

recursive

Question 33

Consider the following recursive definition, where n is a positive integer.
F(1) = 3
F(n) = F(n - 1) + 1 if n > 1
The value of F(3) is _____.

Answer 33

5

Question 34

The recursive algorithm must have one or more base cases, and the general solution must eventually be reduced to
a(n) ___________

Answer 34

base case

Question 35

Recursive algorithms are implemented using ____________________ functions

Answer 35

recursive

Question 36

Consider the following code.
int fact(int num)
{
if (num == 0)
return 1;
else
return num * fact(num - 1);
}
The function fact is an example of a(n) ____________________ recursive function

Answer 36

tail

Question 37

Suppose that function A calls function B, function B calls function C, function C calls function D, and function D calls
function A. Function A is then ____________________ recursive

Answer 37

indirectly

Question 38

If a function A calls a function B and function B calls function A, then function A is ________________
recursive

Answer 38

indirectly

Question 39

If you execute an infinite recursive function on a computer, the function executes until the system runs out of _________

Answer 39

memory

Question 40

The _________ Fibonacci number in a sequence is the sum of the second and third Fibonacci numbers

Answer 40

fourth

Question 41

In the Tower of Hanoi problem, if needle 1 contains three disks, then the number of moves required to move all three
disks from needle 1 to needle 3 is ____.

Answer 41

7