Practical-05

Write a program using a recursive function to find the GCD (Greatest Common Divisor) of two Positive integer numbers.

Introduction

In this program, we will learn to write a recursive function to find the GCD (Greatest Common Divisor) of two Positive integer numbers.

Algorithm

1. Declare a function called "gcd" which will compute the greatest common divisor of two integers.

2. In the "gcd" function, add a terminating condition for when either input is 0. Return 0 in this case.

3. In the "gcd" function, add a condition for when the inputs are equal. Return either input in this case.

4. In the "gcd" function, add a recursive call to compute the gcd of the smaller input and the difference between the two inputs.

5. In the "main" function:

   a. Prompt the user to input two positive integers.

   b. Read the input integers.

   c. Call the "gcd" function with the input integers as arguments.

   d. Print the result.

6. End the program.

Code

Practical-05.c

// Include the stdio header file which contains // the definition of the printf and scanf functions
#include <stdio.h>

// Define a function 'gcd' that takes two
// positive integer numbers as arguments and
// returns the Greatest Common Divisor of them
int gcd(int input1, int input2){

    // Terminating condition if
    // any of the two numbers given is 0
    if(input1 == 0 || input2 == 0)
    {

    }

    // If both numbers given are equal,
    // then return any of them
    if(input1 == input2)
    {
        return input1;
    }

    // Recursive call gcd of the smaller number and
    // the difference of the two numbers
    if(input1 > input2)
    {
        return gcd(input2, input1 - input2);
    }

    return gcd(input1, input2 - input1);
}

// Drive program
void main()
{
    int input1, input2;

    printf("Please input two positive integers\n");
    printf("Number1: ");
    scanf("%d", &input1);
    printf("Number2: ");
    scanf("%d", &input2);

    int result = gcd(input1, input2);
    printf("GCD of %d and %d is: %d\n", input1, input2, result);
}

Output

Please input two positive integers
Number1: 12
Number2: 18
GCD of 12 and 18 is: 6

Explanation

The program first asks the user to enter two positive integers. Then it calls the gcd function to calculate the GCD of the given numbers. The gcd function is a recursive function. It calls itself until the base case is reached. The base case is when either of the two numbers is 0. The GCD of any number and 0 is 0. The gcd function returns the GCD of the given numbers.