Thinking Recursively with Java

11.1. The Control Stack Model

To keep track of this state information through a sequence of method calls, most computers make use of specialized instructions defined in the machine hardware to implement a structure called the control stack. Internally, the control stack consists of an array of consecutive memory locations associated with a stack pointer register (called SP in the remainder of this section) that points to the last item entered on the stack. In most modern hardware architectures, the control stack starts at the highest available addresses in memory and grows toward lower addresses. Because memory is usually diagrammed with the lowest address numbers on top, stack diagrams usually show stacks growing upward from the bottom of the figure (highest addresses) to the top (lowest addresses). The diagrams in this chapter follow this convention and further assume that the highest memory location—and therefore the first element in the control stack—is at the machine address 9999.

Modern computer systems typically include several built-in instructions for manipulating the control stack, of which the most fundamental are traditionally called PUSH and POP. The PUSH instruction takes a value and adds it to the top of the stack. If you start with an empty stack and then push the value 3, the stack looks like this:

Pushing the value 5 results in the configuration

The POP