Program to find HCF using Recursion

Description

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two
numbers is the largest number that divides both of them. 

A simple solution is to find all prime factors of both numbers, then find intersection
of all factors present in both numbers. Finally return product of elements in the intersection.

C/C++

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
/* C Program to find HCF using recursion */
//Save it as HcfUsingRecursion.c
#include<stdio.h>
int main(){
int num1, num2;
printf("Enter first number : ");
scanf("%d",&num1);
printf("Enter second number : ");
scanf("%d",&num2);
int hcf = calculateHCF(num1, num2);
printf("The hcf of %d and %d is %d",num1,num2,hcf);
}
int calculateHCF(int num1, int num2){
if(num2 != 0) {
return calculateHCF(num2, num1%num2);
}else {
return num1;
}
}
/* C Program to find HCF using recursion */ //Save it as HcfUsingRecursion.c #include<stdio.h> int main(){ int num1, num2; printf("Enter first number : "); scanf("%d",&num1); printf("Enter second number : "); scanf("%d",&num2); int hcf = calculateHCF(num1, num2); printf("The hcf of %d and %d is %d",num1,num2,hcf); } int calculateHCF(int num1, int num2){ if(num2 != 0) { return calculateHCF(num2, num1%num2); }else { return num1; } }
/* C Program to find HCF using recursion */
//Save it as HcfUsingRecursion.c

#include<stdio.h>
int main(){

    int num1, num2;

    printf("Enter first number : ");
    scanf("%d",&num1);

    printf("Enter second number : ");
    scanf("%d",&num2);

    int hcf = calculateHCF(num1, num2);

    printf("The hcf of %d and %d is %d",num1,num2,hcf);
}

int calculateHCF(int num1, int num2){
    if(num2 != 0) {

        return calculateHCF(num2, num1%num2);
    }else {

        return num1;
    }
}
Input:
Enter first number : 98
Enter second number : 56

Output:
The HCF of 98 and 56 is 14

Java

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
/* Java Program to find HCF using recursion */
//Save it as HcfUsingRecursion.java
import java.io.*;
import java.util.Scanner;
public class HcfUsingRecursion {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter first number : ");
int num1 = scanner.nextInt();
System.out.println("Enter second number : ");
int num2 = scanner.nextInt();
int hcf = calculateHCF(num1, num2);
System.out.println("The HCF of "+ num1 + " and " + num2 + " is " + hcf);
}
private static int calculateHCF(int num1, int num2) {
if(num2 != 0) {
return calculateHCF(num2, num1%num2);
}else {
return num1;
}
}
}
/* Java Program to find HCF using recursion */ //Save it as HcfUsingRecursion.java import java.io.*; import java.util.Scanner; public class HcfUsingRecursion { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter first number : "); int num1 = scanner.nextInt(); System.out.println("Enter second number : "); int num2 = scanner.nextInt(); int hcf = calculateHCF(num1, num2); System.out.println("The HCF of "+ num1 + " and " + num2 + " is " + hcf); } private static int calculateHCF(int num1, int num2) { if(num2 != 0) { return calculateHCF(num2, num1%num2); }else { return num1; } } }
/* Java Program to find HCF using recursion */
//Save it as HcfUsingRecursion.java

import java.io.*;
import java.util.Scanner;

public class HcfUsingRecursion {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        System.out.println("Enter first number : ");
        int num1 = scanner.nextInt();
        
        System.out.println("Enter second number : ");
        int num2 = scanner.nextInt();
        
        int hcf = calculateHCF(num1, num2);
        
        System.out.println("The HCF of "+ num1 + " and " + num2 + " is " + hcf);
    }

    private static int calculateHCF(int num1, int num2) {
        
        if(num2 != 0) {
            
            return calculateHCF(num2, num1%num2);
        }else {
            
            return num1;
        }		 
    }
}
Input:
Enter first number : 
98
Enter second number : 
56

Output:
The HCF of 98 and 56 is 14

Related Programs

1) Program to calculate power of a number
2) Program to calculate power of a number using recursion
3) Program to Display Fibonacci Series using Recursion
4) Program to calculate factorial using Recursion
5) Program to find sum of digits of a number
6) Program to reverse a number
7) Program to convert Binary to Decimal
8) Program to convert Octal to Decimal
9) Program to calculate square root of a number without using standard library function sqrt()
10) Program to find HCF(Highest Common Factor)/GCD(Greatest Common Divisor) and LCM(Least Common Multiple)
Share Me

Leave a Reply