Control Stack

The control stack (run-time / call stack) holds one activation record per live activation. A call pushes, a return pops, and at any instant the stack is exactly the root-to-node path in the activation tree. Watch it grow and shrink as fib(3) runs.

Definition

Control stack. The control stack (also called the run-time stack or call stack) holds one activation record for each activation that is currently alive — that is, started but not yet finished. A procedure call pushes a record onto the stack; a return pops it off.

At any moment, reading the stack from bottom to top gives exactly the path from the root of the activation tree down to the currently executing activation.

So the control stack is not the whole history of the run — it is a single live snapshot: the chain of callers that are still waiting, ending in the procedure executing right now.

Why a Stack Works

A stack is the right structure because procedure activations are properly nested: whichever activation was called last is the first to finish. A callee always returns before its caller resumes — calls never overlap partway.

This is precisely LIFO (last-in, first-out) order, which is what a stack gives you:

call = the newest activation begins → push (becomes top)
return = the newest activation ends → pop (top removed)

Because nesting can never be violated, a return always pops the record that is currently on top — the same one the matching call pushed. No other discipline (queue, random access) is needed.

The Example — Stack Over Time

We trace the shared running program:

Example

int main() { int x = fib(3); print(x); }

int fib(int n) {

if (n < 2) return n;

return fib(n - 1) + fib(n - 2);

}

Its activation tree (root = main), with fib(3) = 2:

main

fib(3)

fib(2)

fib(1)

fib(0)

fib(1)

Now watch the control stack as the program runs. Bottom of the stack is on the left, top on the right.

Example

Event Stack (bottom → top)

────────────────────────────────────── ──────────────────────────────

main starts [main]

main calls fib(3) → push [main, fib(3)]

fib(3) calls fib(2) → push [main, fib(3), fib(2)]

fib(2) calls fib(1) → push [main, fib(3), fib(2), fib(1)] ◄ deepest (left branch)

fib(1) returns 1 → pop [main, fib(3), fib(2)]

fib(2) calls fib(0) → push [main, fib(3), fib(2), fib(0)]

fib(0) returns 0 → pop [main, fib(3), fib(2)]

fib(2) returns 1 → pop [main, fib(3)]

fib(3) calls fib(1) → push [main, fib(3), fib(1)] ◄ right branch

fib(1) returns 1 → pop [main, fib(3)]

fib(3) returns 2 → pop [main]

main finishes print(2) []

Each line is one transition: a call pushes the new activation record onto the top, a return pops the top record off. The stack reaches its maximum depth of 4 at [main, fib(3), fib(2), fib(1)] and never holds two siblings (e.g. fib(2) and the right fib(1)) at the same time — the first must return before the second is called.

Control Stack vs Activation Tree

These two views describe the same run but capture different things:

	Activation tree	Control stack
What it shows	the whole history of the run — every activation that ever happened	a single live snapshot — only activations alive right now
Shape	a tree (caller above callees)	a path: root-to-current-node
Over time	built once, fixed	grows on each call, shrinks on each return
`fib(2)` and right `fib(1)`	both appear (siblings under `fib(3)`)	never on the stack together

The connection: at any instant, the control stack is one root-to-node path through the activation tree.

For example, when execution is deepest on the left branch, the stack is [main, fib(3), fib(2), fib(1)] — exactly the path from the root main down to the leaf fib(1) in the tree. Later, the right fib(1) gives the path [main, fib(3), fib(1)]. The tree contains both fib(1) leaves forever; the stack only ever holds the one currently executing, plus its chain of waiting callers.

Key Points

The control stack holds one activation record per live activation — started but not yet returned.
A call pushes a record; a return pops it. This works because activations are properly nested (LIFO).
Bottom-to-top, the stack is always the root-to-current-node path in the activation tree.
For fib(3), the stack peaks at depth 4 ([main, fib(3), fib(2), fib(1)]); siblings are never on the stack together.
The tree is the entire history; the stack is the current snapshot of it.

Definition

Control stack. The control stack (also called the run-time stack or call stack) holds one activation record for each activation that is currently alive — that is, started but not yet finished. A procedure call pushes a record onto the stack; a return pops it off.

At any moment, reading the stack from bottom to top gives exactly the path from the root of the activation tree down to the currently executing activation.

So the control stack is not the whole history of the run — it is a single live snapshot: the chain of callers that are still waiting, ending in the procedure executing right now.

Why a Stack Works

This is precisely LIFO (last-in, first-out) order, which is what a stack gives you:

call = the newest activation begins → push (becomes top)
return = the newest activation ends → pop (top removed)

Because nesting can never be violated, a return always pops the record that is currently on top — the same one the matching call pushed. No other discipline (queue, random access) is needed.

The Example — Stack Over Time

We trace the shared running program:

Example

int main() { int x = fib(3); print(x); }

int fib(int n) {

if (n < 2) return n;

return fib(n - 1) + fib(n - 2);

}

Its activation tree (root = main), with fib(3) = 2:

main

fib(3)

fib(2)

fib(1)

fib(0)

fib(1)

Now watch the control stack as the program runs. Bottom of the stack is on the left, top on the right.

Example

Event Stack (bottom → top)

main starts [main]

main calls fib(3) → push [main, fib(3)]

fib(3) calls fib(2) → push [main, fib(3), fib(2)]

fib(2) calls fib(1) → push [main, fib(3), fib(2), fib(1)] ◄ deepest (left branch)

fib(1) returns 1 → pop [main, fib(3), fib(2)]

fib(2) calls fib(0) → push [main, fib(3), fib(2), fib(0)]

fib(0) returns 0 → pop [main, fib(3), fib(2)]

fib(2) returns 1 → pop [main, fib(3)]

fib(3) calls fib(1) → push [main, fib(3), fib(1)] ◄ right branch

fib(1) returns 1 → pop [main, fib(3)]

fib(3) returns 2 → pop [main]

main finishes print(2) []

Control Stack vs Activation Tree

These two views describe the same run but capture different things:

	Activation tree	Control stack
What it shows	the whole history of the run — every activation that ever happened	a single live snapshot — only activations alive right now
Shape	a tree (caller above callees)	a path: root-to-current-node
Over time	built once, fixed	grows on each call, shrinks on each return
`fib(2)` and right `fib(1)`	both appear (siblings under `fib(3)`)	never on the stack together

The connection: at any instant, the control stack is one root-to-node path through the activation tree.

Key Points

The control stack holds one activation record per live activation — started but not yet returned.
A call pushes a record; a return pops it. This works because activations are properly nested (LIFO).
Bottom-to-top, the stack is always the root-to-current-node path in the activation tree.
For fib(3), the stack peaks at depth 4 ([main, fib(3), fib(2), fib(1)]); siblings are never on the stack together.
The tree is the entire history; the stack is the current snapshot of it.