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

• A. 5
• B. 9
• C. 15
• D. 17

Hint:

Set up T(n) = 1 + T(n-1) + T(n-2) with T(n)=1 for n<=0, then build up to T(4).

Answer 1

The Correct Option is C

Step 1: Expand the call tree of $mystery(4)$ level by level.
$mystery(4)$ is 1 call. It spawns $mystery(3)$ and $mystery(2)$.
$mystery(3)$ spawns $mystery(2)$ and $mystery(1)$.
$mystery(2)$ (the one under $mystery(4)$ directly) spawns $mystery(1)$ and $mystery(0)$.

Step 2: Keep expanding every non-base-case call until only base cases remain.
Every call with argument $\leq 0$ stops immediately, costing 1 activation with no children. Every call with argument $1$ spawns $mystery(0)$ and $mystery(-1)$, both base cases, so a call to $mystery(1)$ always costs $1 + 1 + 1 = 3$ activations total. A call to $mystery(2)$ spawns $mystery(1)$ (cost 3) and $mystery(0)$ (cost 1), so it costs $1 + 3 + 1 = 5$ activations total.

Step 3: Roll this up to $mystery(3)$ and then $mystery(4)$.
$mystery(3)$ spawns $mystery(2)$ (cost 5) and $mystery(1)$ (cost 3), so it costs $1 + 5 + 3 = 9$ activations total.
$mystery(4)$ spawns $mystery(3)$ (cost 9) and $mystery(2)$ (cost 5), so it costs $1 + 9 + 5 = 15$ activations total.

Step 4: Sanity check against the stack description.
Since each call stays on the stack only while it is active and is popped once it returns, the "total number of function calls" being asked for is the count of every push that ever happens, not the maximum stack depth at any one time. Adding up every push in the tree built above gives 15.

Final Answer:
There are 15 total function-call activations to compute $mystery(4)$, matching option (C).