FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 13: Recursion

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 21

Essay

Review LaterAdd Note

Review Later

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.

Correct Answer

verified

The binary search examines the midpoint ...

View Answer

Show Answer

Question 22

Essay

Review LaterAdd Note

Review Later

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?

Correct Answer

verified

Half the array is eliminated i...

View Answer

Show Answer

Question 23

Essay

Review LaterAdd Note

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

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.

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

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

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.

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 recursive function can have only one recursive case.

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?

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?

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

A binary search works with any array of numbers.

A recursive function can have only one stopping case.

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

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); } }

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

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?

A recursive function can have local variables.

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?