Stack frames

The call stack

A call stack is a data structure used to store details of currently running subroutines. Each subroutine will be represented by a stack frame made up of a return address, parameters for the subroutine, and Local variables belonging to the subroutine.
The parameters are the values passed into the subroutine e.g. for a subroutine drawSquare this may be the x and y coordinates to draw it at and the length of each side. Local variables are those defined within a subroutine that exist only while the subroutine remains in the call stack. As soon as it finishes executing we can no longer access its local variables.
The return address specifies which subroutine control should be passed back to when a subroutine finishes executing. When a subroutine calls another subroutine the point at which it may be resumed is also part of the return address.

Stack frame example

Consider a subroutine drawLogo that draws two offset squares and is itself made up of two calls to a procedure drawSquare that itself consists of 4 calls to a procedure drawLine.

Recursion and stack frames

Recursive algorithms call themselves. Each successive call to their own subroutine must have a separate frame on the call stack as it will have different parameters and possibly different local variables. This means as it unwinds, each result can be popped off the stack one after the next and used to provid ea solution to the previous call.

Underflow and overflow

Stack underflow occurs when we try to pop an item from an empty stack.

Stack overflow happens when we try to push an item to a full stack

Knowledge check

Knowledge for this sectio will be tested with the recursion information on the next page.