Deck 15: Recursion

Question 1

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 << recFunc(8)<< endl;

A) 4
B) 8
C) 72
D) 720

Answer 1

D

Question 2

In a recursive function,the base case stops the recursion.

Answer 2

True

Question 3

With recursion,the base case must eventually be reduced to a general case.

Answer 3

False

Question 4

Every call to a recursive function requires the system to allocate memory for the local variables and formal parameters.

Question 5

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

Question 6

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 << recFunc(10)<< endl;

A) 10
B) 11
C) 100
D) 110

Question 7

void printNum(int num) //Line 1
{ //Line 2
if (n < 0) //Line 3
cout << "Num is negative" << endl; //Line 4
else if (num == 0) //Line 5
cout << "Num is zero" << endl; //Line 6
else //Line 7
{ //Line 8
cout << num << " "; //Line 9
printNum(num - 1); //Line 10
} //Line 11
} //Line 12
Consider the accompanying definition of a recursive function.Which of the statements represent the base case?

A) Statements in Lines 3 and 4
B) Statements in Lines 5 and 6
C) Statements in Lines 3-6
D) Statements in Lines 5-10

Question 8

The following is an example of a recursive function,where nextNum is a function such that nextNum(x)= x + 1.
int recFunc(int x)
{
return nextNum(nextNum(x));
}

Question 9

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

Question 10

The following is an example of a recursive function.
void print(int x)
{
if (x > 0)
{
cout << x << " " ;
print (x - 1);
}
}

Question 11

To design a recursive function,you must determine the limiting conditions.

Question 12

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
Tracing through ____ recursion is more tedious than tracing other recursive forms.

A) direct
B) indirect
C) tail
D) iterative

Question 13

int foo(int n) //Line 1
{ //Line 2
if (n == 0) //Line 3
return 0; //Line 4
else //Line 5
return n + foo(n - 1); //Line 6
} //Line 7
Consider the accompanying definition of a recursive function.Which of the statements represents the base case?

A) Statements in Lines 1-6.
B) Statements in Lines 3 and 4.
C) Statements in Lines 5 and 6.
D) Statements in Lines 3, 4, and 5.

Question 14

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

A) step-wise
B) recursive
C) member-wise
D) iterative

Question 15

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
Consider the following definition of the recursive function print. void print(int num)
{
If (num > 0)
{
Cout << num << " ";
Print(num - 1);
}
}
What is the output of the following statement?
Print(4);

A) 0 1 2 3 4
B) 1 2 3 4
C) 4 3 2 1
D) 4 3 2 1 0

Question 16

void printNum(int num) //Line 1
{ //Line 2
if (n < 0) //Line 3
cout << "Num is negative" << endl; //Line 4
else if (num == 0) //Line 5
cout << "Num is zero" << endl; //Line 6
else //Line 7
{ //Line 8
cout << num << " "; //Line 9
printNum(num - 1); //Line 10
} //Line 11
} //Line 12
Consider the accompanying definition of a recursive function.Which of the statements represent the general case?

A) Statements in Lines 3-11
B) Statements in Lines 5-6
C) Statements in Lines 5-11
D) Statements in Lines 7-11

Question 17

int foo(int n) //Line 1
{ //Line 2
if (n == 0) //Line 3
return 0; //Line 4
else //Line 5
return n + foo(n - 1); //Line 6
} //Line 7
Consider the accompanying definition of a recursive function.Which of the statements represent the general case?

A) Statements in Lines 1-6
B) Statements in Lines 3 and 4
C) Statements in Lines 4, 5, and 6
D) Statements in Lines 5 and 6

Question 18

You can use a recursive algorithm to find the largest element in an array.

Question 19

Infinite recursions execute forever on a computer.

Question 20

The ____ case is the case for which the solution is obtained directly.

A) general
B) base
C) direct
D) tail

Question 21

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

A) Recursive
B) Iterative
C) Procedural
D) Step-by-step

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 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 << mystery(5)<< endl;

A) 50
B) 65
C) 120
D) 180

Question 23

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

A) Iterative
B) Recursive
C) Procedural
D) Object

Question 24

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
A function is called ____ if it calls itself.

A) directly iterative
B) indirectly iterative
C) directly recursive
D) indirectly recursive

Question 25

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.

Question 26

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.

Question 27

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

A) one
B) two
C) three
D) four

Question 28

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 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 << mystery(6,10)<< endl;

A) 13
B) 21
C) 40
D) 42

Question 29

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

A) Iterative
B) Direct recursive
C) Indirect recursive
D) Infinite recursive

Question 30

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
If every recursive call results in another recursive call,then the recursive function (algorithm)is said to have ____ recursion.

A) unlimited
B) indefinite
C) infinite
D) tail

Question 31

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 beta[10] = {2,5,8,9,13,15,18,20,23,25};
What is the output of the following statement?
Cout << mystery(beta,4,7)<< endl;

A) 27
B) 33
C) 55
D) 66

Question 32

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 << puzzle(5,10)<< endl;

A) 720
B) 5040
C) 5760
D) 10800

Question 33

Recursive algorithms are implemented using ____________________ functions.

Question 34

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

A) void rFibNum(int a, int b)
B) bool rFibNum(int a, int b)
C) bool rFibNum(int a, int b, int n)
D) int rFibNum(int a, int b, int n)

Question 35

int recFunc(int num)
{
if (num >= 10)
return 10;
else
return num * recFunc(num + 1);
}
A recursive function in which the last statement executed is the recursive call is called a(n)____ recursive function.

A) direct
B) tail
C) indefinite
D) indirect

Question 36

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

Question 37

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 ____________________.

Question 38

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

A) Only two disks can be moved at a time.
B) You can remove disks only from the first needle.
C) The removed disk must be placed on one of the needles.
D) A larger disk can be placed on top of a smaller disk.

Question 39

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 << puzzle(3,7)<< endl;

A) 10
B) 21
C) 42
D) 420

Question 40

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 << mystery(alpha,0,4)<< endl;

A) 1
B) 18
C) 27
D) 35

Question 41

If you execute a(n)____________________ recursive function on a computer,the function executes until the system runs out of memory.

Question 42

Let x be an integer.We call the ____________________ of x after division by 2 the rightmost bit of x.

Question 43

The collating sequence of A in the ASCII character set is ____________________.

Question 44

The ____________________ bit of 33 is 1.

Question 45

The language of a computer,called ____________________ language,is a series of 0s and 1s.

Question 46

The fourth Fibonacci number in a sequence is the sum of the ____________________ Fibonacci numbers.

Question 47

The numbering system that the computer uses is called the ____________________ system.

Question 48

If a function A calls function B and function B calls function A,then function A is ____________________ recursive.

Question 49

A(n)____________________ control structure is used to control the repeated calls in recursion.

Question 50

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 ____________________.