GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
170 views
int func(int n) {
    if(n<3)
    return 1;
    else 
    return func(n-1)+func(n-3)+1;
}

How many invocations for calculating func(func(5))

 

asked in Programming by Veteran (50.9k points)   | 170 views
Do we need to save the function calls in a table after calculating or every function call is a fresh call ?
Every call is a fresh - there is no saving in the given code.
Yes, Sir right and also they have not mentioned anything :P

1 Answer

+7 votes
Best answer

$F(5) = F(4) + F(2) + 1$

$F(4) = F(3) + F(1) + 1$

$F(3) = F(2) + F(0) + 1$ 

Hence, Solving all gives $F(5) = 7$ with $3$ distinct invocations.


$F(7) = F(6) + F(4) + 1$

$F(6) = F(5) + F(3) + 1$

$F(5) = F(4) + F(2) + 1$

$F(4) = F(3) + F(1) + 1$

$F(3) = F(2) + F(0) + 1$

And, Solving all gives $F(7) = 17$ with $8$ invocations, assuming there is no saving in the above code.

Or,

 

answered by Veteran (47.9k points)  
edited by
Will add a art work later :)
Yes, Sure :)


Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users