Recursion - Data Structures and Abstractions with Java - page 167

displayArray(0, numberOfEntries - 1);
} // end display
private void displayArray( int first, int last)
{

System.out.println(bag[first]);
if (first < last)
displayArray(first + 1, last);
} // end displayArray

Note: A recursive method that is part of an implementation of an ADT often is private,
because its use requires knowledge of the underlying data structure. Such a method is unsuit-
able as an ADT operation.

Recursively Processing a Linked Chain

7.20

We can illustrate the recursive processing of a chain of linked nodes by performing a simple task
such as displaying the data in the chain. Once again, we'll implement the method display for the
ADT bag, but this time let's use the linked implementation introduced in Chapter 3. That imple-
mentation defines the field firstNode as a reference to the first node in the chain.
Dividing a linked chain into pieces is not as easy as dividing an array, since we cannot access any
particular node without traversing the chain from its beginning. Hence, our first approach displays the
data in the first node and then recursively displays the data in the rest of the chain. Thus, as it did in
Segment 7.19, display will call a private recursive method. We will name that method displayChain .
As a recursive method, displayChain needs an input value. That input should represent the chain, so
we give displayChain a parameter that references the first node in the chain.
Suppose that we name displayChain 's parameter nodeOne . Then nodeOne.getData() is the
data in the first node, and nodeOne.getNextNode() is a reference to the rest of the chain. What
about the base case? Although a one-element array was a fine base case for displayArray , using an
empty chain as the base case is easier here because we can simply compare nodeOne to null . Thus,
we have the following implementations for the methods display and displayChain :

public void display()
{

displayChain(firstNode);
} // end display
private void displayChain(Node nodeOne)
{

if (nodeOne != null )
{

System.out.println(nodeOne.getData()); // display first node
displayChain(nodeOne.getNextNode()); // display rest of chain

} // end if
} // end displayChain

Note: When you write a method that processes a chain of linked nodes recursively, you use
a reference to the chain's first node as the method's parameter. You then can process the first
node followed by the rest of the chain.