CodeCrucks

CodeCrucks

Program to Find GCD of Two Numbers using Recursion

Program to Find GCD of Two Numbers using Recursion

by · Published · Updated

  • Write a program to Find GCD of Two Numbers using Recursion in C
  • Write a program to Find GCD of Two Numbers using Recursion in C++
  • Write a program to Find GCD of Two Numbers using Recursion in Python
  • Write a program to Find GCD of Two Numbers using Recursion in PHP
  • Write a program to Find GCD of Two Numbers using Recursion in Java
  • Write a program to Find GCD of Two Numbers using Recursion in Java Script
  • Write a program to Find GCD of Two Numbers using Recursion in C#

Explanation:

The greatest number that divides two integers without leaving a residual is known as the GCD (Greatest Common Divisor). Euclid’s Algorithm serves as the foundation for the reasoning used to calculate the GCD using recursion.

Recursive Algorithm

  1. Define a Function:
    • gcd(a, b) that takes two integers a and b.
  2. Base Case:
    • If b == 0, return a.
  3. Recursive Case:
    • Return gcd(b, a % b).

Program to Find GCD of Two Numbers using Recursion

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);

    printf("GCD of %d and %d is %d\n", a, b, gcd(a, b));
    return 0;
}


#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;

    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b) << endl;
    return 0;
}


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

a = int(input("Enter the first number: "))
b = int(input("Enter the second number: "))

print(f"GCD of {a} and {b} is {gcd(a, b)}")


<?php
function gcd($a, $b) {
    if ($b == 0)
        return $a;
    return gcd($b, $a % $b);
}

echo "Enter the first number: ";
$a = intval(trim(fgets(STDIN)));
echo "Enter the second number: ";
$b = intval(trim(fgets(STDIN)));

echo "GCD of $a and $b is " . gcd($a, $b) . "\n";
?>


import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the first number: ");
        int a = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int b = scanner.nextInt();

        System.out.println("GCD of " + a + " and " + b + " is " + gcd(a, b));
    }
}


function gcd(a, b) {
    if (b === 0)
        return a;
    return gcd(b, a % b);
}

const a = parseInt(prompt("Enter the first number:"));
const b = parseInt(prompt("Enter the second number:"));

console.log(`GCD of ${a} and ${b} is ${gcd(a, b)}`);


using System;

class Program {
    static int GCD(int a, int b) {
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }

    static void Main() {
        Console.Write("Enter the first number: ");
        int a = int.Parse(Console.ReadLine());
        Console.Write("Enter the second number: ");
        int b = int.Parse(Console.ReadLine());

        Console.WriteLine($"GCD of {a} and {b} is {GCD(a, b)}");
    }
}

List of All Programs