Skip to content
GATEiit

GATE CSE 2021 Set 2 Q33: Value returned by a subtraction-based recursive function

Question

Consider the following ANSI C function:

int SomeFunction(int x, int y)
{
  if ((x == 1) || (y == 1)) return 1;
  if (x == y) return x;
  if (x > y) return SomeFunction(x - y, y);
  if (y > x) return SomeFunction(x, y - x);
}

The value returned by SomeFunction(15, 255) is ________.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 15 (official GATE 2021 final answer key)

Concept used: Repeated subtraction of the smaller from the larger is Euclid's GCD algorithm.

First step: Subtract 15 from 255 repeatedly: 255, 240, …, 15, at which point x=yx = y.

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 →