|
|
|
|
|
|
|
In the example for finding the minimum using recursion, the size of the problem was the length of the array being searched. When the array length became 1, the solution was known. If there is only one array element, it is clearly the minimum (as well as the maximum). |
|
|
|
|
|
|
|
|
In the Towers of Hanoi game, the size of the problem was the number of disks to be moved. When there was only one left on the beginning peg, it could be moved to its final destination. |
|
|
|
|
|
|
|
|
1. What distinguishes the base case from the recursive case in a recursive algorithm? (pp.1120-1121) |
|
|
|
|
|
|
|
|
2. What is the base case in the Towers of Hanoi algorithm? (pp. 1127-1132) |
|
|
|
|
|
|
|
|
3. In working with simple variables, the recursive case is often stated in terms of a smaller value. What is typical of the recursive case in working with structured variables? (pp. 1132-1142) |
|
|
|
|
|
|
|
|
4. In printing a linked list in reverse order recursively, what is the base case? (pp. 1135-1137) |
|
|
|
|
|
|
|
|
Answers 1. The base case is the simplest case, the case where the solution can be stated nonrecursively. 2. When there are no more circles left to move. 3. It is often stated in terms of a smaller structure. 4. When the value of the current node pointer is NULL. |
|
|
|
|
|
|
|
|
Exam Preparation Exercises |
|
|
|
|
|
|
|
|
1. Recursion is an example of: |
|
|
|
 |
|
|
|
|
a. selection |
|
|
|
|
|
|
|
|
b. a data structure |
|
|
|
|
|
|
|
|
c. repetition |
|
|
|
|
|
|
|
|
d. data-flow programming |
|
|
|
|
|
|
|
|
2. A void function can be recursive, but a value-returning function cannot. (True or False?) |
|
|
|
|
|
|
|
|
3. When a function is called recursively, the actual parameters and automatic local variables of the calling version are saved until its execution is resumed. (True or False?) |
|
|
|
|
|
|
|
|
4. Given the recursive formula F(N) = -F(N-2), with base case F(0) = 1, what are the values of F(4), F(6), and F(5)? (If any of the values are undefined, say so.) |
|
|
|
|
|
|
|
|
5. What algorithm error(s) lead to infinite recursion? |
|
|
|
|
|
|
|
|
6. What control structure appears most commonly in a recursive function? |
|
|
|
|
|
|
|
|
7. If you develop a recursive algorithm that employs tail recursion, what should you consider? |
|
|
|
|
|
|
|
|
8. A recursive algorithm depends on making something smaller. When the algorithm works on a data structure, what may become smaller? |
|
|
|
|
|
|
|
|
a. Distance from a position in the structure. |
|
|
|
|
|
|
|
|
b. The data structure. |
|
|
|
|
|
|
|
|
c. The number of variables in the recursive function. |
|
|
|
|
|
|
|
|
9. What is the name of the memory area used by the computer system to save information for pending recursive calls of a function? |
|
|
|
|
|