GATE 2026 DA Q.39: solution and answer

GATE 2026 · DAQ.39 · 2 marks · MCQ

A recursive function in Python is given.

def mystery(n):
    if n <= 0:
        return 1
    else:
        return mystery(n-1) + mystery(n-2)

Now, consider the following function call:

mystery(4)

Assume that a typical runtime stack is used to manage function calls. Each function call is pushed onto the stack and removed only after it finishes execution.

Which of the following options denotes the total number of function calls (i.e., the total number of stack activations), including the initial call, to compute mystery(4)?

(A)
5
(B)
9
(C)
15
(D)
17

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (C): mystery(4) makes 15 function calls in total, counting the initial call.

Official answer: CSource: Official answer key, GATE 2026 DA (IIT Guwahati)

Let $C (n)$ be the number of activations (including the first one) when mystery(n) is called.
Base case: if n <= 0 the function returns 1 at once and makes no further calls, so $C (n) = 1$ for every $n \leq 0$ . In particular $C (0) = C (- 1) = 1$ .
Recursive case: for n > 0 the call counts once and then makes mystery(n-1) and mystery(n-2), so $C (n) = 1 + C (n - 1) + C (n - 2)$ .
$C (1) = 1 + C (0) + C (- 1) = 1 + 1 + 1 = 3$ .
$C (2) = 1 + C (1) + C (0) = 1 + 3 + 1 = 5$ .
$C (3) = 1 + C (2) + C (1) = 1 + 5 + 3 = 9$ .
$C (4) = 1 + C (3) + C (2) = 1 + 9 + 5 = 15$ .
Check with the call tree: every call with $n > 0$ has exactly two children, and every call with $n \leq 0$ is a leaf. Let $L (n)$ be the number of leaves. Then $L (n) = 1$ for $n \leq 0$ and $L (n) = L (n - 1) + L (n - 2)$ otherwise, giving $L (1) = 2$ , $L (2) = 3$ , $L (3) = 5$ , $L (4) = 8$ . A full binary tree with 8 leaves has $8 - 1 = 7$ internal calls, so the total is $8 + 7 = 15$ .

KEY IDEA

Count activations, not the returned value. The recurrence is $C (n) = 1 + C (n - 1) + C (n - 2)$ with $C (n) = 1$ for $n \leq 0$ . Note that n <= 0 makes both $n = 0$ and negative $n$ base cases.

WATCH OUT FOR

Treating only n == 0 as a leaf, or forgetting that mystery(n-2) can reach $n = - 1$ , which is also a leaf. Another slip is answering 5 (the depth plus one) or 9 (the count for mystery(3)), or counting only the leaves (8) or only the internal calls (7).

From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 10 Python questions, with notes

GATE 2026 DA Q.39: solution and answer

Answer and solution

More Python questions