The GATE Grind

GATE 2026 DA – Question 39

Programming, Data Structures and Algorithms · Programming in Python · 2 marks · Multiple choice

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)?

  1. 5
  2. 9
  3. 15
  4. 17

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 15

Explanation

Let $C(n)$ be the number of calls made for the argument $n$. For $n \le 0$ there is just one call, so $C(0) = C(-1) = 1$. For $n > 0$, $C(n) = 1 + C(n-1) + C(n-2)$. Then $C(1) = 1 + 1 + 1 = 3$, $C(2) = 1 + 3 + 1 = 5$, $C(3) = 1 + 5 + 3 = 9$ and $C(4) = 1 + 9 + 5 = 15$.