Chapter 9
Linked Data Structures and Recursion
In this chapter, we look at two advanced programming techniques, recursion and linked data structures, and some of their applications. Both of these techniques are related to the seemingly paradoxical idea of defining something in terms of itself. This turns out to be a remarkably powerful idea.
A subroutine is said to be recursive if it calls itself, either directly or indirectly. What this means is that the subroutine is used in its own definition. Recursion can often be used to solve complex problems by reducing them to simpler problems of the same type.
A reference to one object can be stored in an instance variable of another object. The objects are then said to be "linked." Complex data structures can be built by linking objects together. An especially interesting case occurs when an object contains a link to another object that belongs to the same class. In that case, the class is used in its own definition. Several important types of data structures are built using classes of this kind.
Contents of Chapter 9:
- Section 1: Recursion
- Section 2: Linked Data Structures
- Section 3: Stacks, Queues, and ADTs
- Section 4: Binary Trees
- Section 5: A Simple Recursive Descent Parser
- Programming Exercises
- Quiz on This Chapter