Activation Tree

An activation tree is a tree that depicts how procedure activations are nested in time during one execution of a program. The root is the activation of main. Each node is a single activation (one call), and the children of a node, in left-to-right order, are the activations that node calls, in the order it calls them.

An activation is one live invocation of a procedure — one trip from entering the procedure's body to returning from it. A single procedure (like fib) can have many activations during a run, because it can be called many times; each call is its own node in the tree.

The tree records who called whom and in what order — not the source-code structure. It is a picture of the run, not of the program text.

Procedure calls obey a strict discipline:

If activation a calls activation b, then b begins after a begins and ends before a ends. Activations are properly nested.

This is exactly the rule of balanced parentheses: the lifetime of a callee sits entirely inside the lifetime of its caller — it can never outlive the call that created it and can never start before that caller is running.

Because of this, activation lifetimes either nest one inside another or are completely disjoint — they never partially overlap. That single guarantee is what makes the activation tree a tree and what lets a simple stack manage activations at run time.

We use one running program throughout this chapter.

Running fib(3) unfolds like this: fib(3) calls fib(2) then fib(1); fib(2) calls fib(1) then fib(0); and fib(1) / fib(0) are base cases that return immediately. The final result is fib(3) = 2.

The activation tree for this run:

Why does fib(3) have exactly these two children? Its body evaluates fib(n - 1) + fib(n - 2), which for n = 3 is fib(2) then fib(2)'s sibling fib(1) — so fib(3) makes exactly two calls, left to right. The same body gives fib(2) its two children fib(1) and fib(0). The leaves fib(1), fib(0), and the right-hand fib(1) are base cases (n < 2): they return at once and call nothing, so they have no children.

Reading the tree by time, each activation contributes two events: an enter when it begins and a leave when it returns. For our run the events occur in this order:

Notice the events are perfectly balanced — every enter X is matched by a later leave X, with nothing crossing — which is the nesting property in action.

This event order is exactly a preorder / depth-first (DFS) walk of the activation tree: you enter a node, recursively visit its children left to right, then leave it. The activation tree and the execution trace are two views of the same thing.

Freeze the run at any instant and ask: which activations are currently alive (entered but not yet left)?

The live activations at any moment are exactly the nodes on the path from the root down to the activation that is running right now.

For example, the moment fib(0) is executing, the live activations are main → fib(3) → fib(2) → fib(0) — precisely that root-to-current path. Because these are properly nested, the live set behaves as a stack: entering an activation pushes it, leaving it pops it.

That stack is the control stack (the run-time stack of activation records) — the subject of the next topic.

• An activation tree shows how procedure activations nest in time during one run; the root is main, each node is one activation.
• A node's children, left to right, are the activations it calls, in call order — so the tree encodes who called whom and when.
• Nesting property: if a calls b, then b starts after a starts and ends before a ends — activations are properly nested, like balanced parentheses, and never partially overlap.
• The enter/leave event trace is a preorder (DFS) walk of the tree; the tree and the trace are the same information.
• The live activations at any instant are exactly the root-to-current path, and they form the control stack.