Skip to content
GATEiit

GATE DA 2026 Q39: Number of calls made by a Fibonacci-like recursion

Question

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

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2026 final answer key)

Concept used: Count calls with a recurrence: C(n)=1+C(n−1)+C(n−2)C(n) = 1 + C(n-1) + C(n-2) for n>0n > 0, and C(n)=1C(n) = 1 for n≤0n \le 0.

First step: C(0)=C(−1)=1C(0) = C(-1) = 1, C(1)=3C(1) = 3, C(2)=5C(2) = 5, C(3)=9C(3) = 9, then C(4)=1+9+5C(4) = 1 + 9 + 5.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 DA question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Programming, Data Structures and Algorithms PYQs

PracticePractise Programming, Data Structures and Algorithms questions →Full paperAll GATE DA 2026 questions →