GATE CSE 2007 | Question: 42

Question

Consider the following C function:

int f(int n)
{ 
    static int r = 0;
    if (n <= 0) return 1;
    if (n > 3)
    {   r = n; 
        return f(n-2) + 2;
    }
    return f(n-1) + r;
}

What is the value of $f(5)$?

• A. $5$
• B. $7$
• C. $9$
• D. $18$

Comments

I am getting 18+15 = 33, as answer. 
If I include last return call for f(5), can anyone tell me why we ignoring that ? 

---

Because, we are entering if block which has return in it.

---

---

VARIATION OF THE ABOVE QUESTION

Let's also solve a variation of the above question
{Here, the change is that we are also modifying r when n <= 0}

Note that here r has a storage class of static

The point to note here is that the value of r in f(n-1)+r is evaluated after f(n-1) is evaluated completely.

So in this case, r will be 6 for each f(n-1)+r

f(0)+r=1+6=7
f(1)+r=7+6=13
f(2)+r=13+6=19
f(3)+2=19+2=21

 

Answer 1

The answer is D.

$f(5) = 18.$

$f(3) + 2 = 16 + 2 = 18$

$f(2) + 5 = 11 + 5 = 16$

$f(1) + 5 = 6 + 5 = 11$

$f(0) + 5 = 1+5 = 6$

Consider from last to first. Since it is recursive function.

Comments

no you can not execute two return statement in a single function as soon as the first return statement runs then all the other statement after that return statement will not execute no matter what statements they are.

---

what would be the answer if declaration of variable and its initialisation were on saperate lines?…...my doubt is regarding the fact that static only means that variable only has one copy so used by all calls so r=0 will make r 0 .In current case ...is r=0 ignored because it is combined with declaration  and declaration is only done once. can somone clarify all this??

---

how you have directly written f(5) 18 not understandable please explain clearly

Answer 2

Note: Function calls are retained on the stack.

\begin{align*}
    &\text{int } f(5) \\
    &\quad \downarrow \\
    &f(3) + 2 \quad \text{(18)} \\
    &\quad \downarrow \\
    &f(2) + 5 \quad \text{(16)} \\
    &\quad \downarrow \\
    &f(1) + 5 \quad \text{(11)} \\
    &\quad \downarrow \\
    &f(0) + 5 \quad \text{(6)} \\
    &\quad \downarrow \\
   &1 \quad \text{(base case)} \\
    & \\
    &f(5) = 18 = \text{Ans}
\end{align*}

Answer 3

Option d , solution with recursive tree