Activation records, activation trees, the call stack; caller vs callee duties; recursion

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Which area holds the local variables of a function call? from Lesson 5.1
• How many distinct names does the SSA form of x = a; x = x + 1 have? from Lesson 4.3
• What is the preorder of a tree with root A whose children are B and C, and B has a child D? from Lesson 0.2.4

1 · The Story

📖

A tray per speaking turn

During Mr. Patel’s evening, speakers interrupt each other. Mr. Patel starts; he calls on Mrs. Shah for a figure; she in turn asks the accountant. Each time someone starts, Rhea puts a new tray on the pile with: the questions handed to them, a space for their answer, a note of who asked them and where that person should resume, and room for their own scribbles.

When the accountant answers, his tray comes off, his answer goes into Mrs. Shah’s hands, and she resumes exactly where she left off.

After the evening, Rhea draws a chart of who called on whom, in order: Mr. Patel at the top, below him everyone he called, below them everyone they called. The tray pile at any moment is just one path down that chart: from Mr. Patel to whoever is speaking now.

2 · Predict First

🤔

For fib(4) with fib(n) = fib(n − 1) + fib(n − 2) and fib(0) = 0, fib(1) = 1, how many calls to fib happen in total, and what is the largest number of fib records on the stack at once? Write your guess down. The answer is in the vault.

3 · Core Concept

Activations and the activation tree

Each execution of a procedure body is an activation. Activations are nested in time: if p calls q, q’s activation ends before p’s. The activation tree has a node per activation, with the activations a procedure calls as its children, left to right in call order.

• The sequence of calls is a preorder walk of the tree; the sequence of returns is a postorder walk.
• At any moment, the stack holds exactly the activations on the path from the root to the current node.

The activation record (stack frame)

Each live activation has an activation record (stack frame) on the run-time stack. A typical layout (Dragon book order):

The formal parameters are the names in the procedure’s declaration; the actual parameters (arguments) are the expressions written in the call.

Calling and return sequences

• Calling sequence (split between caller and callee): the caller evaluates the actual parameters, stores the return address and the old stack top (control link) in the new record, and jumps to the callee; the callee saves registers, sets up its locals, and runs.
• Return sequence: the callee places the return value, restores the saved registers and stack top, and jumps to the return address; the caller copies the returned value.

Fields of fixed size (links, saved status) sit in the middle of the record so both sides know their offsets; variable-size data goes at the ends.

Recursion

Every recursive call gets its own record, so each call has its own locals and parameters. The maximum stack depth equals the height of the activation tree (plus the records above it, like main).

Story → compiler term

4 · Visual

Activation tree of fib(4) (from running the program): 9 calls to fib, returns shown under each node.

The stack while fib(1) runs for the first time: exactly the path main → fib(4) → fib(3) → fib(2) → fib(1).

5 · Worked Examples

Example 1 Easy

Draw the activation tree of fib(4) and list the calls in order.

Solution

Calls in preorder: fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0): 9 calls. Returns come in postorder. Rhea’s chart after the evening.

Example 2 Medium

For int f(int n) { if (n <= 1) return 1; return f(n − 1) + f(n − 2); }, how many calls does f(5) make, and what is the largest number of f records on the stack at once?

Solution

calls(n) = 1 + calls(n − 1) + calls(n − 2), with calls(0) = calls(1) = 1: calls(2) = 3, calls(3) = 5, calls(4) = 9, calls(5) = 15. The deepest path is f(5) → f(4) → f(3) → f(2) → f(1): 5 records. f(5) returns 8. All confirmed by running it.

Example 3 GATE

For int t(int n) { if (n <= 0) return 1; return t(n − 1) + t(n − 1) + t(n − 2); }, find the value of t(3), the number of calls and the maximum stack depth of t.

Solution

Values: t(0) = 1, t(−1) = 1, t(1) = 1 + 1 + 1 = 3, t(2) = 3 + 3 + 1 = 7, t(3) = 7 + 7 + 3 = 17. Calls: c(n) = 1 + 2c(n − 1) + c(n − 2) with c(0) = c(−1) = 1 → c(1) = 4, c(2) = 10, c(3) = 25. Depth: t(3) → t(2) → t(1) → t(0): 4.

6 · Shortcuts

⚡

Count calls with a recurrence: calls(n) = 1 + Σ calls(arguments of the recursive calls), base cases = 1. Valid when: call-count questions on recursive functions.

⚡

Maximum stack depth = longest root-to-leaf path in the activation tree (count records, add main if asked). Valid when: stack-depth questions.

7 · GATE Traps

⚠️

• The number of calls is the number of nodes in the activation tree, not its height.
• Max stack depth is the height (+1), not the number of calls.
• The control link points to the caller; the static link has a different job, explained in Lesson 5.3.
• Formal parameters are declared names; actual parameters are the arguments.
• Calls happen in preorder, returns in postorder.

8 · Memory Hook

🧠

One tray per turn; the pile is a path; the chart is a tree.

9 · Connect the Dots

A record’s locals are easy to find. But a procedure can also use names it does not declare. Which declaration does such a name refer to: the one in the surrounding program text, or the one in whoever called it? That is the next lesson, and a GATE favourite.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markCalls

How many calls to g does g(48, 18) make, where int g(int a, int b) { if (b == 0) return a; return g(b, a % b); }?

Numerical answer: ________

Q2NAT2 marksCalls

How many calls to h does h(6) make, where int h(int n) { if (n == 0) return 0; return 1 + h(n − 1); }?

Numerical answer: ________

Q3MCQ1 markLinks

The control link of an activation record points to:

• (A) the lexically enclosing procedure’s record
• (B) the caller’s record
• (C) the heap
• (D) the code of the procedure

Q4MSQ1 markDuties

Which are usually done by the caller in the calling sequence?

• (A) evaluating the actual parameters
• (B) storing the return address
• (C) initialising the callee’s local variables
• (D) saving the old stack top as the control link

Q5MCQ1 markActivation tree

The order in which procedures are called corresponds to which walk of the activation tree?

• (A) preorder
• (B) postorder
• (C) level order
• (D) reverse postorder

11 · Rule Card

• Activation tree: node per activation, children in call order; calls = preorder, returns = postorder.
• Stack holds the root-to-current path.
• Record: actual parameters, returned value, control link, static link, saved status (return address, registers), locals, temporaries.
• Caller: evaluates actuals, saves return address and control link. Callee: saves registers, sets up locals; on return restores and jumps back.
• calls(n) via recurrence; max depth = tree height.

12 · Concept Ledger

activationactivation treeactivation record (stack frame)control link (dynamic link)return addresssaved machine statusformal parameteractual parametercaller / calleecalling sequence / return sequence

13 · Answer Vault