GATE CSE 2021 Set 2 | Question: 49

Question

Consider the following $\text{ANSI C}$ program

#include <stdio.h>
int foo(int x, int y, int q) 
    {
        if ((x<=0) && (y<=0))
        return q;
        if (x<=0)
        return foo(x, y-q, q);
        if (y<=0)
        return foo(x-q, y, q);
        return foo(x, y-q, q) + foo(x-q, y, q);
    }
int main( )
{
    int r = foo(15, 15, 10);
    printf(“%d”, r);
    return 0;
}

The output of the program upon execution is _________

Comments

use memoization whenever possible in this kind of convoluted recursive question. You’ll end up reducing a lot of your work.

---

@palashbehra5,
Yes, This is a good technique.

Answer 1

Single child parent inherit the value of child, double child parents inherit the sum of the value of their children.

The function will return the value $60.$

Comments

answer is 60

---

Perfect !

Answer 2

Here is a traced out Recursive Tree for the above problem.

Answer: 60

Answer 3

Circles in the same color represent the repeated recursion part.

I have named the statements which will be executed at that point of time.

Answer is made considering the beginner point of view. Though, it can be done in shorter space as explained in the best answer.