Program to Find G.C.D Using Recursion - (C# Basic Programs)

Finding the greatest common divisor (G.C.D) of two numbers is a common mathematical problem. In this tutorial, we will discuss a C# program to find the G.C.D using recursion.

Syntax

The general syntax for the recursive method to find G.C.D is as follows:

public static int GCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    }
    else {
        return GCD(num2, num1 % num2);
    }
}

Example

using System;

class Program {
    public static int GCD(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        else {
            return GCD(num2, num1 % num2);
        }
    }

    public static void Main(string[] args) {
        int num1, num2, result;
        Console.Write("Enter the first number: ");
        num1 = int.Parse(Console.ReadLine());
        Console.Write("Enter the second number: ");
        num2 = int.Parse(Console.ReadLine());
        result = GCD(num1, num2);
        Console.WriteLine("GCD of {0} and {1} is {2}", num1, num2, result);
    }
}

Output:

Enter the first number: 24
Enter the second number: 36
GCD of 24 and 36 is 12

Explanation

This program calculates the G.C.D of two numbers using recursion. The GCD method takes two integer parameters num1 and num2, and it returns their G.C.D. The base case for recursion is when num2 becomes 0. In this case, the method simply returns num1. Otherwise, it recursively calls itself with num2 and num1 % num2 as its parameters until the base case is met.

The main method takes two integers as input from the user and calls the GCD method to calculate the GCD of the given numbers. The result is displayed on the console.

Use

This program can be used to calculate the G.C.D of two numbers using recursion. The recursive approach is more memory-efficient than the iterative approach since it uses less memory to store the call stack.

Summary

In this tutorial, we have discussed a C# program to find the G.C.D of two numbers using recursion. We have seen the syntax, example, explanation, use, and important points of using recursion to calculate the G.C.D. By understanding the recursive technique, programmers can use it for other problems that require recursive solutions.