Finding the GCD in JS using Euclid's Algorithm

recursion_using_euclids_algorithm.md

Where Javascript and Recursion Meet Euclid's Algorithm

I'll be explaining recursion utilizing Euclid's Algorithm for finding the greatest common denominator when both variables are greater than zero.

What is Recursion?

Recursion is a mathematical procedure that utilizes a procedure or definition within itself to develop a solution. Now if you're anything like me, reading that statement just appears as a bunch of wordplay. Truth is, recursion is a difficult topic to understand during your initial encounter with it but as time progresses and your experience using recursion grows, you'll grasp the concept with ease and be able to implement recursive solutions into your own code.

Before we start, it's worth mentioning that there are several great articles discussing recursion and the fundamentals of the topic. In writing this, I'm not only providing a tutorial on how recursion works to find the GCD but also assisting myself in completely grasping the concept. I do recommend working through a problem using recursion then writing your own blog post, similar to this one, to help you completely understand the innerworkings of recursion.

A few great articles and tutorials on recursion: https://www.codecademy.com/courses/javascript-lesson-205/0/1 https://www.sitepoint.com/recursion-functional-javascript/ https://msdn.microsoft.com/en-us/library/wwbyhkx4(v=vs.94).aspx http://www.integralist.co.uk/posts/js-recursion.html

Okay, great. With that out of the way, lets get to our solution.

Understanding Euclid's Algorithm

There are many solutions to finding the greatest common denominator (GCD) out there. In this example on recursion, we will be using Euclid's Algorith. Without going into great detail of Euclids solution to finding the GCD, I'll share the specifics and refer you to another source if you care to have a greater understanding of the algorithm. (https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm)

The algorithm I will be using assumes that there are two inputs (num1 and num2) and both inputs are greater than zero. With that being said, we can state several terms to develop our solution.

• gcd(a, a) = a,
• gcd(a, b) = gcd(a-b, b) if a > b,
• gcd(a, b) = gcd(a, b-a) if a < b

Putting these terms into an if...else if statement:

function euclidGCD(num1, num2) {
  var gcd;
  
  if (num1 === num2) {
    gcd = num1;
  } else if (num1 > num2) {
    gcd = euclidGCD((num1 - num2), num2);
  } else if (num1 < num2) {
    gcd = euclidGCD(num1, (num2 - num1);
  }
  
  return gcd;
}

console.log('GCD is: ' + euclidGCD(48, 18));

Let step through lines 6 and 8 to gain a complete understanding of what's going on.

Using the arguments 48 and 18 for num1 and num2, respectively, we will walk through this problem.


Evaluate 48 === 18 => false
Evaluate 48 > 18 => true
  - Assign gcd = euclidGCD((48 - 18 = 30), 18)
    - Evaluate 30 === 18 => false
    - Evaluate 30 > 18 => true
      - Assign gcd = euclidGCD((30 - 18 = 12), 18)
        - Evaluate 12 === 18 => false
        - Evaluate 12 > 18 => false
        - Evaluate 12 < 18 => true
          - Assign gcd = euclidGCD(12, (18 - 12 = 6))
            - Evaluate 12 === 6 => false
            - Evaluate 12 > 6 => true
              - Assign gcd = euclidGCD((12 - 6 = 6), 6)
                - Evaluate 6 === 6 => true
              - return gcd 
          - return gcd
      -return gcd
  -return gcd
  
The return value is going to be 6 for each step in the recursive cycle. 

So with this exploration, we're able to point out a couple facts. First off, we know that our program is going to continuously enter into a recursive procedure (calling a function within itself) until we meet our first conditional statement, which is to check to see if num1 === num2. When this conditional returns true, we've found our GCD and can exit the recursive cycle.

Next, if there is not an explicit conditional statement (or a break in other cases) to determine an "end point", recursion will enter an infinite cycle and crash. Just like a loop, recursion continues to loop within itself until there is a breaking condition. In our case, if (num1 === num1) is our breaking condition because we're no longer required to enter another recursive cycle. Therefore, we can move on with our program (at that level) and return the variable gcd which is 6. That process continues as we move up through each level of our recursive cycle and ultimately back into our main program giving us a final return value of 6.

In closing

I hope you enjoyed this short tutorial on recursion. It's an amazing tool to have and put into use if you know how to use it properly. I encourage you to investigate into greater detail the properties of recursion and it's pros/cons. Being an excellent developer is not only know how to use the tools but when they're appropriate to use.

Thank you very much for your explanation, it helped me to understand this problem