c program

Question

Consider the following code:

int f(int num)
{

      int result =0;                                                                                                                                                                             if(num <= 1)
                return 1;
      else
      {
                for(i=num;i>=1;i--)
                         result+=f(i/3);
      }
      return result;
}

Anyone plz explain this code line by line for input num=6????

Answer 1

Follow bottom-up approach in such questions. like first calculate f(0) then f(1) and so on , because there are recursive calls and functions are evaluated in post order so better start from leaf ..

f(0)=1 //obvious

f(1)=1  // obvious

---

f(2)= ?        i=2                                                   i=1

                   r=0+f(2/3)=0+f(0)=1                     r=1+f(1/3)=1+f(0)=1+1=2                  

f(2)=2

---

f(3)=?    i=3                                                i=2                                i=1

              r=0+f(3/3)=0+f(1)=0+1=1        r=1+f(2/3)=1+1=2        r=2+f(1/3)=2+1=3

f(3)=3

---

f(4)=?  

  i=4                                        i=3                                          

  r=0+f(4/3)=0+f(1)=1          r=1+f(3/3)=1+f(1)=2              

  i=2                                                  i=1

r=2+f(2/3)=2+f(0)=3                     r=3+f(1/3)=4

f(4)=4

---

f(5)=?

i=5                                               i=4                                        i=3                                 

r=0+f(5/3)=0+f(1)=1                 r=1+f(4/3)=2                       r=2+f(3/3)=2+f(1)=3    

   i=2                                   i=1

  r=3+f(2/3)=3+1=4       r=4+f(1/3)=4+f(0)=5

f(5)=5

---

f(6)=? 

i=6                                                  i=5                                      i=4              

r=0+f(6/3)=0+f(2)=2                    r=2+f(5/3)=3                      r=3+f(4/3)=4  

  i=3                                                     i=2                         i=1

r=4+f(3/3)=5                                      r=5+f(2/3)=6         r=6+f(1/3)=6+f(0)=7

f(6)=7

Comments

can you plzz explain time complexity of the above question ??

Answer 2

f(0)=1,f(1)=1,f(2)=2.

i=6 result=2

i=5 result=3

i=4 result=4

i=3 result=5

i=2 result=6

i=1 result=7