C++ Recursion: Greatest common divisor (GCD) with recursive function

Last update on December 20 2024 12:25:11 (UTC/GMT +8 hours)

Write a C++ program to implement a recursive function to find the greatest common divisor (GCD) of two numbers.

Sample Solution:

C Code:

// Recursive function to find the greatest common divisor (GCD) of two numbers
#include <iostream>

// Function to calculate the greatest common divisor (GCD) of two numbers
int gcd(int x, int y) {
  // Base case: if either number is 0, return the other number as the GCD
  if (x == 0)
    return y;
  if (y == 0)
    return x;

  // Recursively find the GCD by calling the function with (y, x % y)
  return gcd(y, x % y);
}

int main() {
  int n1, n2;
  std::cout << "Input the first number: ";
  std::cin >> n1;
  std::cout << "Input the second number: ";
  std::cin >> n2;

  // Calculate the GCD using recursion
  int result = gcd(n1, n2);

  std::cout << "The GCD of " << n1 << " and " << n2 << " is: " << result << std::endl;

  return 0;
}

Sample Output:

Input the first number: 12
Input the second number: 36
The GCD of 12 and 36 is: 12

Input the first number: 196
Input the second number: 8
The GCD of 196 and 8 is: 4

Explanation:

In the above exercise,

• The "gcd()" function takes two integers x and y as parameters and calculates their greatest common divisor (GCD) using recursion.
• The base case is when x or y is 0. In this case, the function returns the other number as the GCD.
• In the recursive case, the function recursively calls itself with the arguments (y, x % y).
• This recursive step continues until y becomes 0, at which point the function returns x as the GCD.
• The main function prompts the user to enter two numbers, calls the "gcd()" function to calculate their GCD, and then displays the result.

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Reversing a linked list with recursive function.
Next C++ Exercise: Counting occurrences of an element in an array with recursive function.