Search⌘ K
Home
Courses
Recursion for Coding Interviews in C++

Solution Review 1: Find the Greatest Common Divisor

Understand how to implement a recursive function to find the greatest common divisor (GCD) of two integers. This lesson guides you through the base case and recursive calls, illustrating the problem-solving approach with practical C++ code examples.

We'll cover the following...

Solution

C++
#include <iostream>
using namespace std;
int gcd(int num1, int num2)
{
  // base case
  if (num1==num2)
  {
    return num1;
  }
  //recursive case
  if(num1 > num2)
  {
    gcd(num1-num2, num2);
  }
  
  else if(num2 > num1)
  {
    gcd(num1, num2-num1);
  }
}
int main() 
{
  int x=42;
  int y=56;
  // computing gcd and storing it in result
  int result= gcd(42,56);
  // printing result
  cout<<"Greatest Common Divisor of "<<x<<" and "<<y<<" is "<<result; 
  return 0;
}

Understanding the Code

In the code above, the function gcd is a recursive function as it makes a recursive call in the function body. Below is an explanation of the above code:

Driver Function

  • In the main() code, we have defined three integer variables: x,y and result.

  • result stores the greatest common divisor of x and y when the gcd function is called.

  • line 30 ...