Deck 14: Recursion

Question 1

A class member function may be recursive.

Answer 1

True

Question 2

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

Answer 2

iterative

Question 3

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

Answer 3

recursive calls

Question 4

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

Question 5

Every recursive definition may be rewritten iteratively.

Question 6

The operating system uses a stack to control recursion.

Question 7

Recursive functions must return a value.

Question 8

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

Question 9

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 10

Recursive functions always execute faster than an iterative function.

Question 11

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 12

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

Question 13

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 14

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

Question 15

A stack exhibits what behavior?

Question 16

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

Question 17

A recursive function is a function that ______________.

Question 18

Recursive functions may return any type of value

Question 19

Not all recursive definitions may be written iteratively.

Question 20

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

Question 21

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 22

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 23

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 24

A stack exhibits _________ behavior.

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

Question 25

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 26

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 27

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 28

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 29

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 30

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 31

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 32

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 33

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

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 37

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 38

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 39

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 40

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 41

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 42

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 43

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