edited by
17,772 views
60 votes
60 votes

Consider the following recursive C function.

void get(int n)
{
    if (n<1) return;
    get (n-1);
    get (n-3);
    printf("%d", n);
}

If $get(6)$ function is being called in $main()$ then how many times will the $get()$ function be invoked before returning to the $main()$?

  1. $15$
  2. $25$
  3. $35$
  4. $45$
edited by

5 Answers

Best answer
80 votes
80 votes

Answer : Option B

$\text{T(n) = T(n-1) + T(n-3) + 2}$, here $\text{T(n)}$ denotes the number of times a recursive call is made for input $n$. $2$ denotes the two direct recursive calls.

$\text{T(n $\leq0$) = 0}$
$\text{T(1) = 2}$
$\text{T(2) = 4}$
$\text{T(3) = 6}$
$\text{T(4) = 10}$
$\text{T(5) = 16}$
$\text{T(6) = 24}$

So, answer is $\text{24 + 1}$ call from main = $25$.

edited by
4 votes
4 votes

@Arjun Sir I think we can also develop the recurrence like : 

 T(n) = T(n-1) + T(n-3) +1 ; otherwise
 T(n) = 1 ; for  n < 1 

   Which means if the node at which  we are standing is greater than equal to one then we will calculate the calls in (n-1) part + in        (n-3) part + 1 (since the node on which we are standing is also a call) and in case if n<1 then that will yields only 1.

T(1)=3 , T(2)= 3 + 1 + 1 = 5, T(3) = 5 + 1 + 1 = 7 , T(4) = 7 + 3 + 1= 11 , T(5) = 11 + 5 + 1 = 17,
T(6) = T(5) + T(3) + 1 =  17 + 7 + 1 = 25. 

Answer:

Related questions

67 votes
67 votes
11 answers
2
go_editor asked Feb 15, 2015
17,241 views
Let $f(n) = n$ and $g(n) = n^{(1 + \sin \: n)}$, where $n$ is a positive integer. Which of the following statements is/are correct?$f(n) = O(g(n))$$f(n) = \Omega(g(n))$On...
57 votes
57 votes
5 answers
3
44 votes
44 votes
5 answers
4
go_editor asked Feb 15, 2015
10,734 views
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...