CODEWITHSUNDEEP
c++recursion
cout
cout

Reputation: 25

A little confused on this recursion example

int gcd (int a, int b)
{
   if (b == 0)
      return a;
   if (a == 0)
      return b;
   return gcd (b, a % b);
}

What is the result of gcd (5, 15)?

I ended up getting 15 but I'm not sure if it's correct, all the loops are confusing me.

Upvotes: 0

Views: 84

Answers (4)

CodeMonkey
CodeMonkey

Reputation: 4738

gcd (5, 15) returns gcd (15, 5 % 15) == gcd (15, 5), which in turn returns gcd (5, 5 % 15) == gcd (5, 5), which returns gcd (5, 5 % 5) == gcd (5, 0) == 5. So you should be returning 5.

A good way to see what's happening is to insert printf statements at the beginning of the function and at the two final return points showing what happens:

gcd(5,15)
gcd(15,5)
gcd(5,0)
5

An example Python implementation:

def gcd (a, b):
    print("gcd({0},{1})".format(a, b))
    if b == 0:
        print(a)
        return a
    if a == 0:
        print(b)
        return b
    return gcd (b, a % b)

gcd(5,15)

Upvotes: 0

Saurav Sahu
Saurav Sahu

Reputation: 13924

See the recursive calls in this way:

gcd(5, 15)
        |
    gcd(15,  5 (as 5 % 15)  )   // 'b' simply takes position of 'a'
               | 
           gcd(5,  0 (as 15 % 5) )
                     |
                if (b == 0) return a; // a is 5, so returned value is 5.

           return 5;

    return 5; 

return 5;

Upvotes: 0

Colin Schoen
Colin Schoen

Reputation: 2592

Here are the recursive calls that are made in order

gcd(5, 15)
gcd(5, 5) # Because 5 % 15 = 5
gcd(5, 0)

So the return value of gcd(5, 15) is 5

Upvotes: 4

Dishonered
Dishonered

Reputation: 8841

Let a = 5 and b = 15;

In the first loop we check if either of a and b are 0 , they are not so we call

gcd(15,0); because 5%15 = 5.

So a = 15 , b = 5.

we call gcd(5,15%5) i.e gcd(5,0).

The answer is 5;

Upvotes: 0

Related Questions