GATE 2021 CS (CS2) – Question 59
What does this program print?
#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; }Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 60 to 60
Explanation
Each positive coordinate needs two subtractions of ten to become nonpositive. While both are positive, recursion branches on which coordinate is reduced; after one finishes, the remaining reductions are forced. There are C(4,2)=6 distinct interleavings of the two reductions of each coordinate. Every terminal call returns q=10, so the sum is sixty.