Program opened below. You can scroll through the algorithm, Java code and output.
Program 35
HCF Using Recursion
Question
Accept two positive integers and calculate their HCF using recursion.
Algorithm
Step 1: Start the program and accept two positive integers a and b.
Step 2: Check that both entered integers are greater than zero.
Step 3: If either integer is invalid, display an appropriate message and stop.
Step 4: Call the recursive method hcf(a, b).
Step 5: If a and b are equal, return either value as the HCF.
Step 6: If a is greater than b, call hcf(a - b, b).
Step 7: Otherwise call hcf(a, b - a).
Step 8: Continue recursive calls until both arguments become equal.
Step 9: Return the equal value through the chain of recursive calls.
Step 10: Receive the returned value in the main method.
Step 11: Display the HCF of the two numbers.
Step 12: Stop the program.
Java program
Javaimport java.util.*;
class HCFRecursion
{
static int hcf(int a, int b)
{
if (a == b)
{
return a;
}
if (a > b)
{
return hcf(a - b, b);
}
return hcf(a, b - a);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter two positive integers: ");
int a = sc.nextInt();
int b = sc.nextInt();
if (a <= 0 || b <= 0)
{
System.out.println("Enter positive integers only");
return;
}
System.out.println("HCF = " + hcf(a, b));
}
}Sample output
Input: Input: 18 12
Output: HCF = 6