Programming and Problem Solving with Java

(^648) | Recursion

13.3 Recursive Algorithms with Structured Variables

In our definition of a recursive algorithm, we identified two cases: the recursive (or general)

case and the base case for which an answer can be expressed nonrecursively. In the general

case for all our algorithms so far, we expressed one argument in terms of a smaller value each

time. When we use structured variables, however, we often state the recursive case in terms

of a smaller structure rather than a smaller value; the base case occurs when there are no

values left to process in the structure.

Printing the Values in an Array

Let’s write a recursive algorithm for printing the contents of a one-dimensional array of nel-

ements to show what we mean. What is the base case? We have no elements left to print.

What is the general case? We print the item in the first position in the array, and print the

rest of the items.

The recursive case is to print the values in an array that is one element “smaller”; that

is, the size of the array decreases by 1 with each recursive call. The base case occurs when

the size of the array becomes 0—that is, when we have no more elements left to print.

Our arguments must include the index of the first element (the one to be printed). How

do we know when no more elements are left to print (that is, when the size of the array to

be printed is 0)? We have printed the last element in the array when the index of the next

Print Array

ifmore elements

Print the item in the first position

Print the rest of the array