ACompressed recap
🧾
Each procedure call is an activation with an activation record on the stack: parameters, return value, control link (to the caller), static link, saved status (return address, registers), locals, temporaries. The activation tree records who called whom; the stack is the path from the root to the current call; calls are preorder and returns postorder. Count calls with recurrences; stack depth is the tree height.
BMerged rule card
5.2 Activation records, activation trees, the call stack; caller vs callee duties; recursion
- 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.
CInterleaved GATE-style questions
Q1NAT2 marksCalls
How many calls to f does f(5) make for int f(int n) { if (n <= 1) return 1; return f(n − 1) + f(n − 2); }?
Numerical answer: ________
Q2NAT1 markValue
What does p(5) return, for int p(int n) { if (n <= 0) return 1; return 2 * p(n − 1); }?
Numerical answer: ________
Q3NAT2 marksDepth
What is the maximum number of t records on the stack for t(3), int t(int n) { if (n <= 0) return 1; return t(n − 1) + t(n − 1) + t(n − 2); }?
Numerical answer: ________
Q4MCQ1 markRecord
Which field lets a callee resume its caller at the right instruction?
- (A) control link
- (B) return address
- (C) static link
- (D) returned value
Q5MCQ1 markStack
At any moment, the run-time stack contains records for:
- (A) all activations so far
- (B) the activations on the path from the root to the current activation
- (C) only the current activation
- (D) only finished activations
Q6MSQ1 markParameters
In int max(int a, int b) called as max(x + 1, 7), which are true?
- (A) a and b are formal parameters
- (B) x + 1 and 7 are actual parameters
- (C) x is a formal parameter
- (D) the call creates a new activation record
Q7NAT1 markCalls
How many nodes does the activation tree of fib(4) have (fib calls only)?
Numerical answer: ________
Q8MCQ2 marksReturns
In the activation tree, the order in which activations return is:
- (A) preorder
- (B) postorder
- (C) the same as the order of calls
- (D) random
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 152 marks
calls = 1, 1, 3, 5, 9, 15 for n = 0 … 5 (and f(5) = 8).
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q2 Answer: 321 mark
2⁵ = 32 (6 calls).
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q3 Answer: 42 marks
t(3) → t(2) → t(1) → t(0): 4.
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q4 Answer: (B)1 mark
Part of the saved machine status.
- (A) is wrong: That points to the caller’s record, not the instruction.
- (C) is wrong: Used by nested procedures (Lesson 5.3).
- (D) is wrong: Carries the result.
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q5 Answer: (B)1 mark
Finished activations have been popped.
- (A) is wrong: Finished ones are gone.
- (C) is wrong: Callers are still there.
- (D) is wrong: Reversed.
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q6 Answer: (A) (B) (D)1 mark
x is a variable in the caller.
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q7 Answer: 91 mark
9.
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion
Q8 Answer: (B)2 marks
A node returns after all its children.
- (A) is wrong: That is the call order.
- (C) is wrong: Different.
- (D) is wrong: It is determined.
Re-read: Lesson 5.2 — Activation records, activation trees, the call stack; caller vs callee duties; recursion