Day 61: Python Program to Find GCD of Two Numbers Using Recursion

 

def gcd(a, b):

    """

   Function to calculate GCD of two numbers using recursion

    """

    if b == 0:

        return a

    else:

        return gcd(b, a % b)

num1 = int(input("Enter the first number: "))

num2 = int(input("Enter the second number: "))

result = gcd(num1, num2)

print(f"The GCD of {num1} and {num2} is {result}")

#source code --> clcoding.com 

Code Explanation:

1. Function Definition:

def gcd(a, b):

    """

    Function to calculate GCD of two numbers using recursion

    """

def gcd(a, b):

This defines a function named gcd that takes two arguments, a and b.

a and b represent the two numbers for which we want to calculate the Greatest Common Divisor (GCD).

""" ... """

This is a docstring that describes what the function does. It mentions that the function calculates the GCD of two numbers using recursion.

2. Base Case:

    if b == 0:

        return a

if b == 0:

Checks whether b (the second number) is 0.

This is the base case of recursion. When b is 0, the recursion stops.

return a

If b is 0, the function returns the value of a, as the GCD of any number and 0 is the number itself.

Example: GCD(8, 0) → 8.

3. Recursive Case:

    else:

        return gcd(b, a % b)

else:

Executes if b is not 0.

return gcd(b, a % b)

This is the recursive call. The function calls itself with:

b as the new first argument.

a % b (the remainder when a is divided by b) as the new second argument.

This step reduces the size of the problem with each recursive call, eventually reaching the base case where b is 0.

4. Taking User Input:

num1 = int(input("Enter the first number: "))

num1 = int(input("Enter the first number: "))

Prompts the user to input the first number with the message "Enter the first number: ".

input() captures the user’s input as a string.

int() converts the string input to an integer so it can be used in calculations.

The integer value is stored in the variable num1.

num2 = int(input("Enter the second number: "))

num2 = int(input("Enter the second number: "))

Similar to the above, prompts the user to input the second number.

Converts the input string to an integer and stores it in the variable num2.

5. Calling the Function and Storing the Result:

result = gcd(num1, num2)

result = gcd(num1, num2)

Calls the gcd function with num1 and num2 as arguments.

The function computes the GCD of num1 and num2 and returns the result.

The returned GCD is stored in the variable result.

6. Printing the Result:

print(f"The GCD of {num1} and {num2} is {result}")

print(f"...")

Prints the GCD of the two numbers in a formatted message.

F-String (f"..."): Dynamically inserts the values of num1, num2, and result into the string.

Example Output: The GCD of 48 and 18 is 6.