Questions
1. Explain what is meant by the following:
a. base case
b. general (or recursive) case
c. run-time stack
d. binding time
e. tail recursion
2. True or false? If false, correct the statement. Recursive functions:
a. often have fewer local variables than the equivalent nonrecursive routines.
b. generally use while or for statements as their main control structure.
c. are possible only in languages with static storage allocation.
d. should be used whenever execution speed is critical.
e. are always shorter and clearer than the equivalent nonrecursive routines.
f. must always contain a path that does not contain a recursive call.
g. are always less efficient, in terms of Big-O complexity.
3. Use the Three-Question Method to verify the ValueInList function described in this chapter.
The base-case question: Is there a nonrecursive way out of the function, and does the routine work correctly for this base case?
The general-case question: Assuming that the recursive calls work correctly, does the entire function work correctly?
7. Identify the following:
a. the base case or cases of the function Puzzle
b. the general case or cases of the function Puzzle
8. Show what would be written by the following calls to the recursive function Puzzle:
a. cout << Puzzle(14, 10);
b. cout << Puzzle(4, 7);
c. cout << Puzzle(0,0);
9. Given the following function:
int Func(int num)
{
if (num == 0)
return 0;
else
return num + Fun(num + 1);
}
a. Is there a constraint on the values that can be passed as a parameter for this function to answer the Smaller-caller question?
b. Is Func(7) a good call? If so, what is returned from the function?
c. Is Func(0) a good call? If so, what is returned from the function?
d. Is Func(-5) a good call? If so, what is returned from the function?
12. You must assign the grades for a programming class. The class is studying recursion, and students have been given this simple assignment: Write a recursive function SumSquares that takes a pointer to a linked list of integer elements and returns the sum of the squares of the elements. see image.
Assume that the list is not empty.
You have received quite a variety of solutions. Grade the functions that follow, marking errors where you see them.
a. int SumSquares(NodeType* list)
{
return 0;
if (list != NULL)
return (list->info*list->info) + SumSquares(list->next));
}
b. int SumSquares(NodeType* list)
{
int sum = 0;
while (list != NULL)
{
sum = list->info + sum;
list = list->next;
}
return sum;
}
c. int SumSquares(NodeType* list)
{
if (list == NULL)
return 0;
else return list->info*list->info + SumSquares(list->next);
}
d. int SumSquares(NodeType* list)
{
if (list->next == NULL)
return list->infolist->info;
else return list->infolist->info + SumSquares(list->next); }
e. int SumSquares(NodeType* list)
{
if (list == NULL)
return 0;
else
return (SumSquares(list->next) * SumSquares(list->next));
}
15. A sequential search member function of SortedType has the following prototype: void SortedType::Search(int value, bool& found);
a. Write the function definition as a recursive search, assuming linked list implementation.
b. Write the function definition as a recursive search, assuming an array-based implementation.
22. True or false? If false, correct the statement. A recursive solution should be used when:
a. computing time is critical.
b. the nonrecursive solution would be longer and more difficult to write.
c. computing space is critical.
d. your instructor says to use recursion.
32. True or False? In general, a nonrecursive solution to a problem is more memory efficient than a recursive solution.