GATE 2023 CS Q.36: solution and answer

GATE 2023 · CSQ.36 · 2 marks · MCQ

Consider the following program:

int main()
{
   f1();
   f2(2);
   f3();
   return(0);
}

int f1()
{
   return(1);
}

int f2(int X)
{
   f3();
   if (X==1)
     return f1();
   else
     return (X*f2(X-1));
}

int f3()
{
   return(5);
}

Which one of the following options represents the activation tree corresponding to the main function?

GATE 2023 CS question 36: Four candidate activation (call) trees, each rooted at a node labeled 'main': (A) main has three children f1, f2, f3 (left… — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
Figure — main → (f1, f2, f3); the f2 node → (f3, f2); that inner f2 node → (f3, f1)
(B)
Figure — main → (f1, f2, f3); below → (f3, f1) only (missing one level of recursive nesting)
(C)
Figure — main → (f1); f1 → (f2); f2 → (f3, f1)
(D)
Figure — main → (f1, f2, f3); f2 → (f3, f2, f1) all as one flat row of children

Answer and solution

ANSWER

The activation tree is: main → {f1, f2, f3}; the f2 node → {f3, f2}; that nested f2 node → {f3, f1} — exactly option (A).

Official answer: ASource: Official answer key, GATE 2023 CS (IIT Kanpur)

main() executes, in order: f1(); f2(2); f3(); return(0). So the root node main has three children, in this order: f1, f2, f3.
f1() only executes return(1); it makes no calls, so wherever f1 appears in the tree it is a leaf.
f3() only executes return(5); it makes no calls, so wherever f3 appears in the tree it is a leaf.
f2(2): the body of f2 first (unconditionally) calls f3() — a leaf child. Then it checks X==1; here X==2, so it takes the else branch: return (X*f2(X-1)), which calls f2(2-1) = f2(1). So the children of this f2 node, in call order, are f3 and f2(1).
f2(1): again first calls f3() — a leaf child. Then X==1 is true, so it executes return f1(), calling f1(). So the children of this f2(1) node, in call order, are f3 and f1.
Assembling the whole tree: main → {f1, f2, f3}; the f2 node just created → {f3, f2'}; that nested f2' node → {f3, f1}. This is a 3-level tree under the f2 branch, with main's other two children (f1, f3) remaining leaves.
Comparing to the options: (A) reproduces exactly this structure — main's three children f1,f2,f3; the f2 node's two children f3,f2; that inner f2 node's two children f3,f1. (B) shows only one extra level (f3,f1) directly under f2, omitting the intermediate recursive f2 node — wrong, it collapses two calls into one. (C) makes f1 the sole child of main and puts f2 under f1 — wrong, f1() is called and returns before f2(2) is even called; it is not f2's parent. (D) flattens f3, f2, f1 into one row of siblings under f2 — wrong, it discards the fact that f2(1) is itself a call made by f2(2), with its own two children.
Therefore the correct option is (A).

KEY IDEA

An activation (call) tree mirrors the actual sequence of function calls made during execution, nested exactly as calls are made: if function P calls Q, Q becomes a child of P's node at that call site, in left-to-right call order — it is not the same as the static call graph, and repeated/recursive calls to the same function name create separate, deeper nodes rather than being merged or flattened.

WATCH OUT FOR

Treating "f2 calls f3 then recursively calls f2" as if it collapses into one extra level (option B) or flattens all of f2's descendants into siblings of f2 (option D), instead of correctly nesting each recursive call one level deeper as its own node with its own children — losing track of exactly how many times f2 recurses (here once, from X=2 down to X=1) and forgetting that f3() is called again inside each new invocation of f2.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 9 Recursion questions, with notes

GATE 2023 CS Q.36: solution and answer

Answer and solution

More Recursion questions