Example: GCD using Recursion in Java in Java

// GCD using Recursion
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {

    // Recursive method to find GCD
    public static int findGCD(int a, int b) {
        // Step 1: Base case for the recursion
        // If 'b' is 0, then 'a' is the GCD.
        if (b == 0) {
            return a;
        }
        // Step 2: Recursive step
        // Apply the Euclidean algorithm: GCD(a, b) = GCD(b, a % b)
        return findGCD(b, a % b);
    }

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

        // Step 3: Prompt user for the first number
        System.out.print("Enter the first positive integer: ");
        int num1 = inputScanner.nextInt();

        // Step 4: Prompt user for the second number
        System.out.print("Enter the second positive integer: ");
        int num2 = inputScanner.nextInt();

        // Step 5: Validate input to ensure positive integers
        if (num1 < 0 || num2 < 0) {
            System.out.println("Please enter non-negative integers.");
        } else {
            // Step 6: Call the recursive GCD function and display the result
            int result = findGCD(num1, num2);
            System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + result);
        }

        inputScanner.close();
    }
}