Skip to content
GATEiit

GATE CSE 2021 Set 2 Q59: Output of a doubly recursive function foo(15, 15, 10)

Question

Consider the following 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 ________.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 60 (official GATE 2021 final answer key)

Concept used: Trace the recursion tree; with q fixed at 10 the arguments only take values 15, 5, −5.

First step: Start from the base cases: foo(5, −5) = foo(−5, 5) = 10, then foo(5, 5) = foo(5, −5) + foo(−5, 5).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2021 Set 2 questions →