Deck 14: Recursion

Question 1

In a recursive power function that calculates some base to the exp power, what is the recursive call?

Answer 1

return base * powerbase,exp-1);

Question 2

A stack exhibits what behavior?

Answer 2

Last In - First Out

Question 3

A recursive function is a function that ______________.

Answer 3

calls itself

Question 4

If the recursive function call does not lead towards a stopping case, you have ______________.

Question 5

Recursive functions must return a value.

Question 6

In a recursive power function that calculates some base to a positive exp power, at what value of exp do you stop? The function will continually multiply the base times the value returned by the power function with the base argument one smaller.

Question 7

What is the output of the following code fragment?
int f1int base, int limit)
{
ifbase > limit)
return -1;
else
ifbase == limit)
return 1;
else
return base * f1base+2, limit);
}
int main)
{
cout << f12,4)<return 0;
}

Question 8

Recursive functions may return any type of value

Question 9

Only functions that do not return a value may be recursive.

Question 10

There can be more than one stopping case in a recursive function.

Question 11

You may have at most 1 recursive call in a recursive function.

Question 12

In a recursive function, the statements) that invoke the function again are called the ______________.

Question 13

Not all recursive definitions may be written iteratively.

Question 14

For every recursive solution, there is an) ______________ solution.

Question 15

Recursive functions always execute faster than an iterative function.

Question 16

How do you ensure that your function does not have infinite recursion?

Question 17

A class member function may be recursive.

Question 18

Given the following code fragment, what is the stopping conditions)?
int f1int x, int y)
{
ifx<0 || y<0)
return x-y;
else
return f1x-1,y) + f1x,y-1);
}
int main)
{
cout << f11,2)<return 0;
}

Question 19

Every recursive definition may be rewritten iteratively.

Question 20

The operating system uses a stack to control recursion.

Question 21

A definition that defines a concept or a formula in terms of the concept or formula is called

A) a recursive definition
B) indecision
C) iteration
D) reduction

Question 22

What is wrong with the following recursive function? It should print out the array backwards.
Void printint array[], int start, int size)
{
Ifstart == size)
Return;
Else
{
Printarray, start+1,size);
Cout << array[start] << endl;
}
}

A) infinite recursion
B) the stopping condition is wrong
C) the recursive call is wrong
D) nothing

Question 23

In the following function, how many recursive calls are there?
Void towerschar source, char dest, char help, int numDisks)
{
IfnumDisks<1)
{
Return;
}
Else
{
Towerssource,help,dest,numDisks-1);
Cout << "Move disk from " << source << " to " <Towershelp,dest,source,numDisks-1);
}
}

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

Question 24

What is the output of the following code fragment?
Int f1int n, int m)
{
Ifn < m)
Return 0;
Else ifn==m)
Return m+ f1n-1,m);
Else
Return n+ f1n-2,m-1);
}
Int main)
{
Cout << f15,4);
Return 0;
}

A) 0
B) 2
C) 4
D) 8
E) infinite recursion

Question 25

Every time a recursive function call is executed, a new __________ is put on the top of the stack.

A) Activity frame
B) Activity record
C) program
D) Activation frame

Question 26

A stack exhibits _________ behavior.

A) first in first out
B) last in last out
C) last out first in
D) undefined

Question 27

In order for the binary search to work correctly

A) the list must be sorted
B) the item must exist
C) all of the above
D) none of the above

Question 28

Implementing a task recursively rather than iteratively generally

A) is slower
B) takes more storage memory)
C) is sometimes easier to program
D) all of the above

Question 29

The factorial of an integer is the product of that integer multiplied by all the positive non-zero integers less than that integer. So, 5! ! is the mathematical symbol for factorial) is 5 * 4 * 3*2*1. 4! is 4*3*2*1, so 5! could be written as 5*4!. So a recursive definition of factorial is n! is n*n-1)!, as long as n >1. 1! is 1. What is the recursive call for this function fact)?

A) factn)*n;
B) factn-1)*n;
C) n-1)*factn)
D) factn-2)*n-1)

Question 30

If you try to solve a problem recursively, you should

A) find all the stopping cases and the values if needed at that case
B) find a recursive call that will lead towards one of the stopping cases
C) all of the above
D) none of the above

Question 31

The factorial of an integer is the product of that integer multiplied by all the positive non-zero integers less than that integer. So, 5! ! is the mathematical symbol for factorial) is 5 * 4 * 3*2*1. 4! is 4*3*2*1, so 5! could be written as 5*4!. So a recursive definition of factorial is n! is n*n-1)!, as long as n >1. 1! is 1. What is the stopping case for this function?

A) n<1
B) n==0
C) n==1
D) none of the above

Question 32

What is wrong with the following recursive function? It should print out the array backwards.
Void printint array[], int start, int size)
{
Ifstart == size)
Return;
Else
{
Printarray, start-1,size);
Cout << array[start] << endl;
}
}

A) infinite recursion
B) the stopping condition is wrong
C) the recursive call is wrong
D) nothing

Question 33

Given the following recursive function definition, what is the stopping case?
Void towerschar source, char dest, char help, int numDisks)
{
IfnumDisks<1)
{
Return;
}
Else
{
Towerssource,help,dest,numDisks-1);
Cout << "Move disk from " << source << " to " <Towershelp,dest,source,numDisks-1);
}
}

A) numDisks == 1
B) numDisks >1
C) numDisks < 1
D) numDisks =0

Question 34

What is the output of the following code fragment?
Int f1int n, int m)
{
Ifn < m)
Return 0;
Else ifn==m)
Return m+ f1n-1,m);
Else
Return n+ f1n-2,m-1);
}
Int main)
{
Cout << f15,4);
Return 0;
}

A) 0
B) 2
C) 4
D) 8
E) infinite recursion

Question 35

What is the output of the following code fragment?
Int f1int n, int m)
{
Ifn < m)
Return 0;
Else ifn==m)
Return m+ f1n-1,m);
Else
Return n+ f1n-2,m-1);
}
Int main)
{
Cout << f11,4);
Return 0;
}

A) 0
B) 2
C) 4
D) 8
E) infinite recursion

Question 36

In the binary search program, each time through the list, we cut the list approximately

A) in thirds
B) in quarters
C) by one element
D) in half

Question 37

What is wrong with the following recursive function? It should print out the array backwards.
Void printint array[], int start, int size)
{
Ifstart < size)
Return;
Else
{
Printarray, start+1,size);
Cout << array[start] << endl;
}
}

A) infinite recursion
B) the stopping condition is wrong
C) the recursive call is wrong
D) nothing

Question 38

If your program makes too many recursive function calls, your program will cause a ___________

A) stack underflow
B) activation overflow
C) stack overflow
D) syntax error

Question 39

What is wrong with the following recursive function? It should print out the array backwards.
Void printint array[], int start, int size)
{
Ifstart == size)
Return;
Else
{
Printarray, start-1,size);
Cout << array[start] << endl;
}
}

A) infinite recursion
B) the stopping condition is wrong
C) the recursive call is wrong
D) A and C
E) nothing

Question 40

To ensure that your function recurses correctly and the proper result is reached, you must ensure that

A) all stopping cases are correct
B) all recursive calls lead to one of the stopping cases
C) for each case that involves recursion, that case returns the correct value provided all recursive calls in that case return the correct value.
D) all of the above
E) none of the above

Question 41

What is the output of the following code fragment?
Int f1int base, int limit)
{
Ifbase > limit)
Return -1;
Else
Ifbase == limit)
Return 1;
Else
Return base * f1base+1, limit);
}
Int main)
{
Cout << f12,4)<Return 0;
}

A) 2
B) 3
C) -1
D) 6

Question 42

What is the output of the following code fragment?
Int f1int base, int limit)
{
Ifbase > limit)
Return -1;
Else
Ifbase == limit)
Return 1;
Else
Return base * f1base+1, limit);
}
Int main)
{
Cout << f112,4)<Return 0;
}

A) 2
B) 3
C) -1
D) 6

Question 43

The recursive definition of a Fibonacci Number is Fn) = Fn-1) + Fn-2), where F0)=1 and F1)=1. What is the value of Fib3)?

A) 8
B) 5
C) 2
D) 1

Question 44

The recursive definition of a Fibonacci Number is Fn) = Fn-1) + Fn-2), where F0)=1 and F1)=1. What would be the recursive function call in a recursive implementation of this?

A) return;
B) return fibn) + fibn-1)
C) return fibn-1)+fibn-2)
D) return 1;

Question 45

The square of n can be calculated by noting that squaren) = squaren-1) + diffn-1). diffn) = diffn-1)+2. The square0)=0, diff0)=1. What is the stopping condition for this recursive definition?

A) n=1
B) n=0
C) n=-1
D) unknown

Question 46

What is the output of the following code fragment?
Int f1int x, int y)
{
Ifx<0 || y<0)
Return x-y;
Else
Return f1x-1,y) + f1x,y-1);
}
Int main)
{
Cout << f11,2)<Return 0;
}

A) 0
B) -1
C) 5
D) -5

Question 47

The recursive definition of a Fibonacci Number is Fn) = Fn-1) + Fn-2), where F0)=1 and F1)=1. What is the value of Fib5)?

A) 8
B) 5
C) 2
D) 1

Question 48

What is the output of the following code fragment?
Int f1int x, int y)
{
Ifx<0 || y<0)
Return x-y;
Else
Return f1x-1,y) + f1x,y-1);
}
Int main)
{
Cout << f12,1)<Return 0;
}

A) 0
B) -1
C) 5
D) -5