// Program 35: HCF Using Recursion

import 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));
    }
}