Deck 13: Recursion

Question 1

A design technique is to break a problem into smaller tasks,with the prospect that a smaller problem will be easier to solve.If the smaller task is the identical to the original task excepting only that the size is smaller,the problem may be solved using a recursive algorithm,and implemented with a recursive function.

Answer 1

True

Question 2

The activation frames in nested function calls are handled in a last-in/ first-out order.

Answer 2

True

Question 3

Consider the recursive function, int rec(int n)
{
If (1 ==n )
Return 1;
Else
Return rec(n-1)+ 2*n - 1;
}
Which of these expressions could replace a call to this function?

A)n2 - 1
B)n2 + 1
C)n2
D)(n + 1)2
E)(n - 1)2

Answer 3

C

Question 4

A recursive function can have local variables.

Question 5

A recursive function can have only one recursive case.

Question 6

Each activation frame contains all the function's code,as well as the automatic variables and formal parameters.

Question 7

The binary search algorithm in the text makes recursive on subarrays of the array passed to the algorithm.The index values of the array the algorithm searches run from first to last.The subarrays are dermined using the mid-point.How is the mid point calculate?

A)mid = (first - last)/2;
B)mid = (first + last)/2;
C)mid = (first + last)%2;
D)mid = (first - last)%2;

Question 8

You are doing a binary search of the dictionary for page where a word should be,using the recursive binary search.What is done to guarantee that the successive dictionaries to be searched are smaller?

A)Search a dictionary with one less page.
B)Search a dictionary with one less word.
C)Search a dictionary with half the words.
D)Recursively search the half the dictionary where the word should be.

Question 9

It is proper for a recursion to run on without ending.

Question 10

A recursive function must not return a value.

Question 11

A binary search works with any array of numbers.

Question 12

Here is recursive function.Identify the recursive case and the default case.
void recursive( int i )//a)
{
if ( i < 8 ) //b)
{
i++;//c)
recursive(i);//d)
cout << i << " ";//e)
}
}
//f)The base case is not explicitly listed.If you choose this answer,
// then you must explain what the base case is.

Question 13

A recursive function is a function whose definition contains a call to the function being defined

Question 14

Give the output of the recursive function below when called with an argument of 5. void recursive( int i )
{
Using namespace std;
If ( i < 8 )
{
I++;
Recursive(i);
Cout << i << " ";
}
}

A)6 7 8
B)5 6 7
C)8 7 6
D)7 6 5
E)None of the above.This is an infinite recursion if the function is called with argument 5.

Question 15

In recursion,it is unnecessary to decide whether a stopping case has been reached.

Question 16

Each recursion causes a new activation frame to be placed on the stack.

Question 17

A recursive function can have only one stopping case.

Question 18

You are doing a binary search of the dictionary for page where a word should be,using the recursive binary search What are stopping cases?

A)The dictionary being searched has one page.
B)The second half the dictionary being searched has one page.
C)The middle of the dictionary is at page one.
D)The dictionary being searched has one word

Question 19

A proper recursive solution requires at least two cases: a recursive function that calls the recursive function with a smaller problem,and a base,or stopping case.

Question 20

For the binary search in the text to work,the element searched for must actually be present in the array.

Question 21

Give the three criteria for a correct value being returned by a recursive function.

Question 22

Give a general outline of a successful recursive function definition.

Question 23

Write a recursive function
double recSum(double array[],int count);
that takes an int argument and returns the sum of count array entries.

Question 24

Iterative solutions are always possible.Why then,would we bother with recursive solutions to problems? What advantages do some recursive algorithms have over the iterative versions?

Question 25

In the binary search,each pass (recursion or iteration)selects a subproblem of the original problem to solve.What fraction of the array sent to an initial call is eliminated in the next iterative pass or recursive call?

Question 26

In the binary search,if the array being searched has 32 elements in it,how many elements of the array must be examined to be certain that the array does not contain the key? What about 1024 elements? Note: the answer is the same regardless of whether the algorithm is recursive or iterative.

Question 27

Here is a recursive function.Write an iterative version of it.Hint: Be sure you get the number of copies of "Hip" right.
void rec_cheers(int n)
{
using namespace std;
if(1==n)
cout << "Hurray!" << endl;
else
{
cout << "Hip,";
rec_cheers(n-1);
}
}

Question 28

Write a recursive version of this iterative function:
int g(int n)
{
int h = 1;
while (n > 1)
{
h = h * n;
n--;
}
return h;
}

Question 29

The binary search algorithm in the text makes recursive calls on subarrays of the array passed to the algorithm.The range passed to the search function is first to last.The search algorithm makes recursive calls on the left or right subarray that target will be in,if the target is present.What are the left and right ends of the right subarray?

A)Last ,mid - 1
B)last ,mid + 1
C)mid - 1,last
D)mid + 1,last
E)last,mid

Question 30

Overloading and recursion look similar.Both situations call functions with the same name.Explain the difference.

Question 31

Here is an iterative function.Write a recursive function that does the same thing.Be sure you write the correct number of copies of the cheer,"Hip,Hip,Hurray!".For this problem,ignore namespace issues.
void iter_cheers(int n)
{
for(int i = 0;i < n-1;i++)//this is the tricky part!
cout << "Hip,";
cout << "Hurray!" << endl;
}

Question 32

Explain in your own words what recursion means (in connection with definitions of ideas and as a programming technique. )

Question 33

The binary search algorithm in the text makes recursive on subarrays of the array passed to the algorithm.The range passed to the search function is first to last.The search algorithm makes recursive calls on the left or right subarray that target will be in,if the target is present.What are the left and right ends of the left subarray?

A)first,mid - 1
B)first,mid + 1
C)mid - 1,left
D)mid + 1,left
E)left,mid

Question 34

Here is a recursive function that is supposed to return the factorial.Identify the line(s)with the logical error(s).Hint: This compiles and runs,and it computes something.What is it?
int fact( int n )//a
{
int f = 1;//b
if ( 0 == n || 1 == n )//c
return f;//d
else
{
f = fact(n - 1);//f
f = (n-1)* f;//g
return f;//h
}
}

Question 35

Describe the stack memory (or data)structure.Give a four-word description of the stack discipline.

Question 36

Write a recursive void function that has one parameter which is a positive integer.When called,the function is to write its arguments to the screen backward: If the argument is 1234,the output should be.4321.

Question 37

Give the three criteria for a correct recursive void-function.

Question 38

Give the recursive binary search algorithm.

Question 39

In both the iterative and the recursive binary search,explain why the condition for halting the routine with the variable found assigned false is first > last.

Question 40

How does the computer keep track of all the calls to a recursive function?