CODEWITHSUNDEEP
javarecursion
robert
robert

Reputation: 249

How does recursion works in this code to find GCD?

I came across this codes for finding the GCD of an array of numbers from here

//Function to return gcd of a and b 
static int gcd(int a, int b) { 
    if (a == 0) {
        return b;
    }
    return gcd(b % a, a); 
} 
// Function to find gcd of array of 
// numbers 
static int findGCD(int arr[], int n) { 
    int result = arr[0]; 
    for (int i = 1; i < n; i++) {
        result = gcd(arr[i], result); 
    }
    return result; 
}

The method gcd uses a recursive call gcd(b % a, a). So how does this recursive call works? I know the basics of how a recursion works but I am a little confused on how the gcd method on this piece of code uses recursion. Can anyone please explain to me simply, how the gcd method works in this code?

Upvotes: 0

Views: 645

Answers (3)

WJS
WJS

Reputation: 40047

To help understand recursive methods it is often useful to place print statements in key locations so you can follow what is happening.

By calling the method with specifically chosen prime factors, it is easy to ensure a particular gcd.

In the example below, 3 is the only common factor so it will be the gcd of the two numbers.


    public class RecursiveGCD {

       public static void main(String[] args) {
          System.out.println("GCD = " + gcd(2 * 3 * 4 * 4 * 5, 3 * 7 * 11));
       }
       public static int gcd(int a, int b) {
          System.out.println("\nFinding gcd of a=" + a + " and b=" + b);
          if (a == 0) {
             System.out.println("a == 0 so returning b (gcd) = " + b);
             return b;
          }
          System.out.println(
                "Remainder non-zero, calling with gcd(b % a,  a) = gcd(" + (b % a)
                      + ", " + a + ").");
          return gcd(b % a, a);

       }
    }

Upvotes: 1

Thomas Weller
Thomas Weller

Reputation: 59483

Given two numbers, 12 and 8:

gcd(12,8) calculates b%a = 12%8 = 4 and then calls gcd(4, 8). It does not return yet, because that last call is not completed yet.

gcd(4,8) calculates b%a = 8%4 = 0 and then calls gcd(0,4). That one does not return yet as well, because that call is active.

gcd(0,4) branches into the first if-statement and returns 4.

That defines the return value of gcd(4,8), so the pending call returns 4 as well.

That again defines the return value of gcd(12,8), so the final result is still 4.

The math behind it is also interesting.

I think the main question is: why can we reduce gcd(12,8) to gcd(4,8)?

We assume that there is any result g that can divide 12 without a remainder and 8 without a remainder.

We can split the 12 into g*n (4*3) and 8 into g*m (4*2).

Next, we can say 12-8 = gn-gm = g*(n-m) (4*(3-2)=4). Therefore g does not only divide 12 and 8 without remainder, but also 12-8 (4).

You can do that for even lower numbers: 12-8-8 = gn-gm-gm=g(n-m-m) (4*(3-2-2)=-4). And so on.

The same is true for larger numbers: 12+8 = gn+gm = g*(n+m) (4*(3+2)=20). And you can repeat that by adding 8 numerous times.

The smallest positive number you can get by this approch is 12%8, because you can subtract 8 from 12 for so many times until its remainder is left.

Upvotes: 1

YouKnowWhoIAm
YouKnowWhoIAm

Reputation: 344

Let's take two numbers 24 and 60, and you called the function as gcd(24, 60), then the function stack executes as follows,

gcd(24,60) => 60%24 = 12
gcd(24,12) => 12%24 = 12 (Switch happens)
gcd(12,24) => 24%12 = 0
gcd(0 ,12) => terminates

So switch that happens at step two is the important one because the call basically swaps two numbers, just like you do in an iterative way, think of it like shorthand way.

I could take the same example with 60 and 24 as the first call, then gcd(60,24) would execute as

gcd(60,24) => 24%60 = 24 (Switch happens)
gcd(24,60) => 60%24 = 12 and this follows the same pattern as the above

Here the switch happens because the functions send b%a to the next function as a and a to the function as b.

Upvotes: 1

Related Questions