JavaScript Program to Find G.C.D Using Recursion
The greatest common divisor (G.C.D) of two integers is the largest positive integer that divides both numbers without leaving a remainder. In JavaScript, finding the greatest common divisor (G.C.D) of two numbers using recursion is a common programming task. Recursion is a powerful technique where a function calls itself to solve smaller instances of the same problem until it reaches a base case.
Below are the approaches to finding the G.C.D using recursion in JavaScript:
Syntax:
function functionName(parameters) {
// Base case
if (condition) {
// Return value or perform action
} else {
// Recursive call
functionName(modifiedParameters);
// Additional computation (optional)
}
}
Using recursion
Using the Euclidean algorithm, we define a recursive function to find the G.C.D of two numbers. The Euclidean algorithm is widely used for computing the greatest common divisor of two integers. It relies on the principle that the G.C.D of two numbers also divides their difference, which helps reduce the problem into simpler subproblems until a base case is reached. This approach offers a clear and concise solution leveraging the power of recursion in JavaScript.
Example: To demonstrate finding the greatest common divisor (G.C.D) of two numbers through recursive calls, utilizing the property G.C.D(a, b) = G.C.D(b, a % b).
Javascript
function gcdRecursive(a, b) { // Base case if (b === 0) { return a; } // Recursive case return gcdRecursive(b, a % b); } const num1 = 36; const num2 = 48; console.log(`G.C.D of ${num1} and ${num2} is: ${gcdRecursive(num1, num2)}`); |
G.C.D of 36 and 48 is: 12
Using subtraction algorithm
This approach employs the subtraction algorithm, which repeatedly subtracts the smaller number from the larger one until both numbers become equal, finding the G.C.D of the original numbers. This method offers simplicity and effectiveness in G.C.D computation through recursion.
Example: In the base case, if a equals b, it means we have found the G.C.D. In the recursive cases, we subtract the smaller number from the larger one until both become equal.
Javascript
function gcdRecursiveSubtraction(a, b) { // Base case if (a === b) { return a; } // Recursive cases if (a > b) { return gcdRecursiveSubtraction(a - b, b); } else { return gcdRecursiveSubtraction(a, b - a); } } // Example usage const num1 = 36; const num2 = 48; console.log(`G.C.D of ${num1} and ${num2} is: ${gcdRecursiveSubtraction(num1, num2)}`); |
G.C.D of 36 and 48 is: 12
Using binary euclidean algorithm
This approach utilizes the binary Euclidean algorithm, which is an optimized version of the Euclidean algorithm that uses bitwise operations. It efficiently computes the G.C.D of two numbers by halving the numbers until one of them becomes zero, providing a faster G.C.D computation through recursion.
Example: In the base cases, if one of the numbers is zero, the G.C.D is the other number. We recursively call the function until we find the base case, adjusting the numbers according to the binary Euclidean algorithm’s logic.
Javascript
function gcdRecursiveBinaryEuclidean(a, b) { // Base cases if (a === 0) { return b; } if (b === 0) { return a; } // If both numbers are even if ((a & 1) === 0 && (b & 1) === 0) { return gcdRecursiveBinaryEuclidean(a >> 1, b >> 1) << 1; } // If 'a' is even and 'b' is odd else if ((a & 1) === 0) { return gcdRecursiveBinaryEuclidean(a >> 1, b); } // If 'a' is odd and 'b' is even else if ((b & 1) === 0) { return gcdRecursiveBinaryEuclidean(a, b >> 1); } // If both numbers are odd and 'a' > 'b' else if (a >= b) { return gcdRecursiveBinaryEuclidean((a - b) >> 1, b); } // If both numbers are odd and 'a' < 'b' else { return gcdRecursiveBinaryEuclidean(a, (b - a) >> 1); } } // Example usage const num1 = 36; const num2 = 48; console.log( `G.C.D of ${num1} and ${num2} is: ${gcdRecursiveBinaryEuclidean(num1, num2)}`, ); |
G.C.D of 36 and 48 is: 12
Contact Us