Register

GO Classes Scholarship 2023 | Test | Question: 27

• edited by
568 views
2 votes
2 votes

What will be the number of recursive calls for $\textsf{mystery(5)}$ including the first call?

void mystery(int n) {
    if (n == 0 || n == 1) return 0;
    mystery(n-2);
    printf("%d", n);
    mystery(n-1);
}
• edited by
User Avatar

3 Answers

6 votes
6 votes

here m() is stands for mystery()

and p() for printf()

User Avatar
4 votes
4 votes

Here, $\implies$ indicates number of recursive calls are _ (including the initial call).

$mystery(0) \implies self =  1$.

$mystery(1) \implies self = 1$.

$mystery(2) \implies 1 + 1 + self = 3$.

$mystery(3) \implies 1 + 3 + self = 5$.

$mystery(4) \implies 3 + 5 + self = 9$.

$mystery(5) \implies 5 + 9 + self = 15$.

Answer :- 15.

User Avatar
1 votes
1 votes
The recurrence relation to count number of function calls would be $T(n) = T(n-1) + T(n-2) + 1$ with $T(1) = T(0) = 1$ as base case.

The $+1$ is for the call to itself. E.g., $T(2) = T(1) + T(0) + 1 = 1 + 1 + 1 = 3$

Likewise, you can find T(3) then T(4) and then T(5) which is asked in the question.

OR, you can solve the recurrence relation and then put n = 5.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
3 answers
4
GO Classes asked Aug 6, 2022
438 views
GO Classes Scholarship 2023 | Test | Question: 26
What will be the output of the following C program? int sum = 0; for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++){ sum += i * j; }
What will be the output of the following C program?int sum = 0; for (int i = 1; i <= 10; i++) for (int j = 1; j <= 10; j++){ sum += i * j; }
User Avatar
Link Copied!