654
5.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. 648–651)
6.Which control structures are used to implement recursion? (pp. 651–652)
7.Which control structures are used to implement iteration? (pp. 651–652)
8.In the binary search algorithm, what is the base case? (p. 651)
9.Which of the algorithms presented in this chapter are better implemented us-
ing iteration? (pp. 651–652)
Answers
1.The essential ingredient in a recursive definition is the repetition of the problem in terms of a smaller ver-
sion of itself.2.The base case is the simplest case—that is, the case for which the solution can be stated non-
recursively.3.The size of the problem is the power to which the number is taken. It is decreased by one in
each call.4.There are no more circles left to move.5.It is often stated in terms of a smaller structure.
6.Selection 7.Looping 8.The search area is empty or the item is found.9.Factorial, power, printing values in
an arrayExam Preparation Exercises
1.Recursion is an example of
a.Selection
b.A data structure
c. Repetition
d.Data-flow programming
2.A void method can be recursive, but a value-returning method cannot. (True or
False?)
3.When a method is called recursively, the arguments and local variables of the
calling version are saved until its execution resumes. (True or False?)
4.Given the recursive formula F(N) = F(N2), with a base case of 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) leads to infinite recursion?
6.What control structure appears most commonly in a recursive method?
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 algo-
rithm 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 method
9.What is the name of the memory area used by the computer system to store a
method’s parameters and local variables?