Finding Greatest Common Divisor Using Recursion

Introduction

In mathematics, the greatest common divisor (GCD) of two numbers is commonly defined as the largest positive integer that divides the two numbers without leaving a remainder. In this lab, we will learn to write a C program to find the GCD of two numbers using recursion.

Note: You need to create the file ~/project/main.c yourself to practice coding and learn how to compile and run it using gcc.

cd ~/project
## create main.c
touch main.c
## compile main.c
gcc main.c -o main
## run main
./main

Skills Graph

Reading the input numbers

First, we need to take two integer input numbers from the user to find their GCD. We will use scanf() function to read the input.

#include<stdio.h>

int main()
{
    int a, b;
    printf("Enter two numbers to find GCD of: \n");
    scanf("%d%d", &a, &b);
    // rest of the code
    return 0;
}

Defining the recursive function to find GCD

We will use a recursive function to find the GCD of the two input numbers. The recursive function will have two integer parameters. The function will continue to call itself until two numbers have the same value and return that value as the GCD.

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Calling the recursive function from the main function

In this step, the recursive function will be called with the two input numbers (a and b). The return value of the recursive function will be stored in an integer variable (gcd).

int gcd = find_gcd(a, b);
printf("GCD of %d and %d is: %d\n", a, b, gcd);

Full example code

#include <stdio.h>

// declaring the recursive function
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Enter two numbers to find GCD of: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("GCD of %d and %d is: %d\n", a, b, gcd);
    return 0;
}

// defining the function
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

Summary

In this lab, we learned to write a C program to find the GCD of two numbers using recursion. We utilized a recursive function to calculate the GCD by having the function call itself with modified input parameters until it reaches a base case. This program can be used for solving mathematical problems that require the calculation of the GCD of two numbers.