Find GCD Using Functions

Introduction

In this lab, you will learn how to find the Greatest Common Divisor (GCD) of two numbers using functions in C++. The GCD is the largest number that divides both of the given numbers. We will use a recursive approach to implement the function.

Create a new C++ file

Create a new C++ file called main.cpp in the ~/project directory.

touch ~/project/main.cpp

Include Libraries

In the file, include the necessary libraries.

#include<iostream>

Define the Function to Calculate GCD

Define a recursive function gcd() that takes two integer arguments as input and returns an integer as output, which will be the GCD of the two input numbers.

int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    else if (a == b)
        return a;
    else if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

Write the Main Function

In the main() function, declare two integer variables and assign values to them. Then, call the gcd() function with the two variables as parameters and output the result.

int main() {
    int a = 105, b = 30;
    std::cout << "GCD of " << a << " and " << b << " is " << gcd(a,b) << std::endl;
    return 0;
}

Compile and Run the Program

Save the changes you made to the file and exit. Compile the program using the terminal command given below:

g++ main.cpp -o main

To run the program, enter the following command in the terminal:

./main

Output

After running the program, the output will be displayed in the terminal as:

GCD of 105 and 30 is 15

Summary

In this lab, you learned how to find the Greatest Common Divisor (GCD) of two numbers using a recursive function in C++. This is a useful application in computer science and mathematics.