Question

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

• A. 5
• B. 15
• C. 25
• D. 20

Hint:

For functions with two recursive calls like $F(n) = F(n-1) + F(n-2)$, the number of calls grows exponentially. The recurrence for the number of calls is often $T(n) = 1 + T(n-1) + T(n-2)$. Drawing the call tree is a reliable method for small values of n.

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
We need to count the total number of times the `mystery` function is called to compute `mystery(4)`. This includes the initial call and all subsequent recursive calls. 
Step 2: Recurrence for Call Count: 
Let T(n) be the number of calls to compute `mystery(n)`.
- The call to `mystery(n)` itself is 1 call.
- It then calls `mystery(n-1)` and `mystery(n-2)`.
- So, the total number of calls is $T(n) = 1 + T(n-1) + T(n-2)$.
- The base case `if n <= 0` involves one call and then it returns. So, $T(0) = 1$, $T(-1) = 1$. 
Step 3: Calculating the Number of Calls: 
- `T(0) = 1`
- `T(-1) = 1`
- `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`
Alternatively, we can draw the recursion tree: 

Total nodes = 1 + 2 + 4 + 6 + 2 = 15. 
Step 4: Final Answer: 
The total number of function calls made to compute mystery(4) is 15.