Question:
A recursive function is given:
def mystery(n):
if n $<=$ 0:
return 1
else:
return mystery(n-1) + mystery(n-2)
Find the value of mystery(4).
A recursive function is given:
def mystery(n):
if n $<=$ 0:
return 1
else:
return mystery(n-1) + mystery(n-2)
Find the value of mystery(4).
Show Hint
When evaluating a simple recursive function like this, it's often safer and faster to compute the values iteratively from the bottom up, rather than drawing a large recursion tree. This avoids recomputing the same values multiple times and reduces the chance of error. This technique is known as dynamic programming or memoization.
Updated On: Feb 23, 2026
Hide Solution
Verified By Collegedunia
Correct Answer: 8
Solution and Explanation
Step 1: Understanding the Question:
We are given a recursive function `mystery(n)` and asked to calculate its value for an input of `n=4`. The function's definition is similar to the Fibonacci sequence, but with different base cases.
Step 2: Analyzing the Recurrence Relation:
- Recurrence: `mystery(n) = mystery(n-1) + mystery(n-2)` for n> 0.
- Base Cases: `mystery(n) = 1` for n $\le$ 0. This means `mystery(0) = 1` and `mystery(-1) = 1`, `mystery(-2) = 1`, etc.
Step 3: Calculating the Values Iteratively:
We can compute the values from the base cases up to n=4.
- `mystery(0) = 1` (by base case)
- `mystery(1) = mystery(0) + mystery(-1)`. Since -1 $\le$ 0, `mystery(-1) = 1`.
`mystery(1) = 1 + 1 = 2`
- `mystery(2) = mystery(1) + mystery(0) = 2 + 1 = 3`
- `mystery(3) = mystery(2) + mystery(1) = 3 + 2 = 5`
- `mystery(4) = mystery(3) + mystery(2) = 5 + 3 = 8`
Step 4: Final Answer:
The value of mystery(4) is 8.
We are given a recursive function `mystery(n)` and asked to calculate its value for an input of `n=4`. The function's definition is similar to the Fibonacci sequence, but with different base cases.
Step 2: Analyzing the Recurrence Relation:
- Recurrence: `mystery(n) = mystery(n-1) + mystery(n-2)` for n> 0.
- Base Cases: `mystery(n) = 1` for n $\le$ 0. This means `mystery(0) = 1` and `mystery(-1) = 1`, `mystery(-2) = 1`, etc.
Step 3: Calculating the Values Iteratively:
We can compute the values from the base cases up to n=4.
- `mystery(0) = 1` (by base case)
- `mystery(1) = mystery(0) + mystery(-1)`. Since -1 $\le$ 0, `mystery(-1) = 1`.
`mystery(1) = 1 + 1 = 2`
- `mystery(2) = mystery(1) + mystery(0) = 2 + 1 = 3`
- `mystery(3) = mystery(2) + mystery(1) = 3 + 2 = 5`
- `mystery(4) = mystery(3) + mystery(2) = 5 + 3 = 8`
Step 4: Final Answer:
The value of mystery(4) is 8.
Was this answer helpful?
0
0
Top Questions on Programming Languages
- 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, []))- GATE DA - 2026
- Computer Science
- Programming Languages
- Assume a typical runtime stack is used for the recursive function mystery(n) as defined earlier. How many total function calls (stack activations), including the initial call, are made to compute mystery(4)?
- GATE DA - 2026
- Computer Science
- Programming Languages
def fun(L, i=0):
if i $>=$ len(L) - 1:
return 0
if L[i]> L[i+1]:
L[i+1], L[i] = L[i], L[i+1]
return 1 + fun(L, i+1)
else:
return fun(L, i+1)
data = [5, 3, 4, 1, 2]
count = 0
for _ in range(len(data)):
count += fun(data)
print(count)
- GATE DA - 2026
- Computer Science
- Programming Languages
- 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 S
Which of the following is/are correct?- GATE DA - 2026
- Computer Science
- Programming Languages
- Which file extension is typically used for Python script files?
- IPU CET - 2025
- Computer Awareness
- Programming Languages
View More Questions
Questions Asked in GATE DA exam
- Rishi and Swathi are students of Class 5. Pavan and Tanvi are students of Class 4. Rishi and Pavan are boys. Swathi and Tanvi are girls. These four students played a total of three games of chess. The games were played one after another. A player who lost a game did not participate in any more games. It was observed that:
1. The first game was the only game where two students of the same class played against each other.
2. The students of Class 5 won more games than the students of Class 4.
3. The boys won 2 games and the girl won 1 game.
The student who did not lose any game is:- GATE DA - 2026
- Logical Reasoning
Consider two distinct positive numbers \( m, n \) with \( m > n \). Let \[ x = n^{\log_n m}, \quad y = m^{\log_m n}. \] The relation between \( x \) and \( y \) is -
- GATE DA - 2026
- Logarithms
- Consider the supervised learning task. The objective function being minimized is \( f(w) = w \cdot x \), where \( w \in \mathbb{R} \) is the parameter. Stochastic Gradient Descent with learning rate of 0.10. Let \( w = 10.00 \) be the \( i^{\text{th}} \) iteration (\( w_i \)). The value of \( w \) at the end of iteration \( (i+1) \) is if \( x = 10 \) ________. Round off 2 decimal.
- GATE DA - 2026
- Machine Learning
- The value of \[ \sum_{j=0}^{\infty} \sum_{i=1}^{\infty} 2^{-j} 3^{-i} \] is ________.
- GATE DA - 2026
- Sequences and Series
- Consider the Ridge LRR is being used to learn prediction function \( y_{\text{pred}} = w^T x \) where \( w, x \in \mathbb{R}^2 \) & mean absolute error (MAE) is used to measure the prediction error. A weight of 0.20 is associated with the regularizer. At an intermediate step of training process assume that the parameter \( w = [-3.00, 4.00]^T \). In the next step for the I/P \( x = [1.00, 2.00]^T \), the predicted value of \( y \) is noted. Let the relation b/w \( x = [x_1, x_2]^T \) & the true value of \( y \) be \( y_{\text{true}} = x_1 + x_2 \). The value of the overall regularized loss for instance is __________ (upto 2 decimal).
- GATE DA - 2026
- Machine Learning
View More Questions