How Recursion Works: The Activation Stack

The pseudo-code for the printList function can only be implemented in what we call "a stack based language". These languages keep track of all the functions, which have been invoked at runtime using a data structure called the activation stack. They allow functions to call themselves, by saving their state (local variables and parameters) on a stack, and invoking them again.

Everytime a function is called, its entire state including its local variables and pass by value parameters are saved as a record on the stack. When the function exits, its corresponding record is popped off this stack.

A recursive call would therefore push a record of the function on the stack. Then, the base case would start a process called "unwinding recursion" and slowly the records would be popped off the stack.

The diagram above shows the activation stack for printList. Note how the system preserves various copies of the printList function, with each copy having its own value of the variable i. The stack is built until the condition for the base case holds true. After that the records from the stack are popped off.