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 recursive function in Python is given.
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
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)?Show 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).
Updated On: Jul 22, 2026
- 5
- 9
- 15
- 17
Show Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
Step 1: Set up a formula for the total number of calls.
Let \(T(n)\) be the total number of function-call activations made while computing \(mystery(n)\), counting the call itself. For \(n \leq 0\), the function returns immediately with no further recursive calls, so \(T(n) = 1\) in that base case. For \(n > 0\), the call makes 1 activation for itself, plus it calls \(mystery(n-1)\) and \(mystery(n-2)\), contributing all of their activations too. So
\[ T(n) = 1 + T(n-1) + T(n-2), \quad n > 0 \]
Step 2: Compute the base cases.
\(T(0) = 1\) (base case, no recursive calls).
\(T(-1) = 1\) (also a base case, since \(-1 \leq 0\)).
Step 3: Build up \(T(1)\) through \(T(4)\) using the recursion.
\(T(1) = 1 + T(0) + T(-1) = 1 + 1 + 1 = 3\)
\(T(2) = 1 + T(1) + T(0) = 1 + 3 + 1 = 5\)
\(T(3) = 1 + T(2) + T(1) = 1 + 5 + 3 = 9\)
\(T(4) = 1 + T(3) + T(2) = 1 + 9 + 5 = 15\)
Step 4: Double check by picturing the call tree shape.
\(mystery(4)\) calls \(mystery(3)\) and \(mystery(2)\); \(mystery(3)\) calls \(mystery(2)\) and \(mystery(1)\); and so on, exactly mirroring the Fibonacci recursion tree. Counting every node in this tree, including leaves that hit the base case, gives the same total of 15.
Step 5: Compare with the options.
5 would be \(T(2)\), and 9 would be \(T(3)\); both undercount by stopping the recursion too early. 17 does not match any correct partial sum of this recursion. 15 matches \(T(4)\) computed above.
Final Answer:
The total number of function calls to compute \(mystery(4)\) is 15, which is option (C).
Let \(T(n)\) be the total number of function-call activations made while computing \(mystery(n)\), counting the call itself. For \(n \leq 0\), the function returns immediately with no further recursive calls, so \(T(n) = 1\) in that base case. For \(n > 0\), the call makes 1 activation for itself, plus it calls \(mystery(n-1)\) and \(mystery(n-2)\), contributing all of their activations too. So
\[ T(n) = 1 + T(n-1) + T(n-2), \quad n > 0 \]
Step 2: Compute the base cases.
\(T(0) = 1\) (base case, no recursive calls).
\(T(-1) = 1\) (also a base case, since \(-1 \leq 0\)).
Step 3: Build up \(T(1)\) through \(T(4)\) using the recursion.
\(T(1) = 1 + T(0) + T(-1) = 1 + 1 + 1 = 3\)
\(T(2) = 1 + T(1) + T(0) = 1 + 3 + 1 = 5\)
\(T(3) = 1 + T(2) + T(1) = 1 + 5 + 3 = 9\)
\(T(4) = 1 + T(3) + T(2) = 1 + 9 + 5 = 15\)
Step 4: Double check by picturing the call tree shape.
\(mystery(4)\) calls \(mystery(3)\) and \(mystery(2)\); \(mystery(3)\) calls \(mystery(2)\) and \(mystery(1)\); and so on, exactly mirroring the Fibonacci recursion tree. Counting every node in this tree, including leaves that hit the base case, gives the same total of 15.
Step 5: Compare with the options.
5 would be \(T(2)\), and 9 would be \(T(3)\); both undercount by stopping the recursion too early. 17 does not match any correct partial sum of this recursion. 15 matches \(T(4)\) computed above.
Final Answer:
The total number of function calls to compute \(mystery(4)\) is 15, which is option (C).
Was this answer helpful?
0
0
Top GATE DA Data Science and Artificial Intelligence Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions
Top GATE DA Programming in Python Questions
- Consider the following Python code :
def count (child_dict, i) :
if i not in child_dict.keys() :
return 1
ans = 1
for j in child_dict[i] :
ans += count (child_dict, j)
return ans
child_dict = dict()
child_dict [0] = [1, 2]
child_dict [1] = [3, 4, 5]
child_dict [2] = [6, 7, 8]
print (count(child_dict,0))
Which ONE of the following is the output of this code ? - Consider the function computes (X) whose pseudocode is given below :
\(\frac{\text{computeS (X)}}{S[1] ←1}\)
for i ← 2 to length(X)
S[i] ← 1
if X[i-1] ≤ X[i]
S[i] ← S[i] + S[i - 1]
end if
end for
return S
Which ONE of the following values is returned by the function computeS (X) for X= [6, 3, 5, 4, 10] ? - Consider the following Python function :
def fun (D, s1, s2) :
if s1 s2:
D[s1], D[s2] = D[s2], D[sl]
fun (D, s1+1, s2-1)
What does this Python function fun () do? Select the ONE appropriate option below. - Consider the given Python program.
Which of the following is the correct output of this program?def append_to_lst(val, lst=[]): lst.append(val) return lst print(append_to_lst(1)) print(append_to_lst(2)) print(append_to_lst(3, [])) - Consider the given Python program.
def outer(): x = [] def inner(val): x.append(val) return x return inner f1 = outer() f2 = outer() print(f1(10)) # Line P print(f1(20)) # Line Q print(f2(30)) # Line R print(f1(40)) # Line SWhich of the following options is/are correct?
View More Questions
Top GATE DA Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions