Gate Algo & ds

Question

#include <stdio.h>
int f(int n)
{
    if(n ≤ 1)
        return 1;
    if(n%2 = = 0)
        return f(n/2);
    return f(n/2) + f(n/2+1);
}
int main()
{
    printf("%d", f(11));
    return 0;
}

(a) Stack Overflow (b) 3 (c) 4 (d) 5
 

Comments

You instead should have run it to get an explanation... Anyways, here is the stack

                             f(11)
                     f(5)      +    f(6)
               f(2)   +   f(3)            f(3)
              f(1)     f(1) + f(2)     f(1) + f(2)
               1        1    f(1)       1      f(1)
               1        1     1         1       1

Answer 1

draw the recursion tree

Answer 2

the answer of this question is option d

try to draw recursion tree of the give code.

Answer 3

the above program having IF case without else condition simply solve using tree method.

Comments

SIR ...what DFS traversal from left to right mean here...?

---

evaluate like infix expression(left,root,right)???????

Answer 4

Start with small values....

F(1)=1

F(2)=F(1)=1

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

F(11)=F(5)+F(6)=F(2)+F(3)+F(3)=1+2+2=5