Python Program to Find the GCD Using Recursion

Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The GCD is also known as the greatest common factor (GCF) or the highest common factor (HCF).

One of the most efficient algorithms to find the GCD is Euclid’s algorithm, which can be implemented using recursion. The algorithm is based on the principle that the GCD of two numbers also divides their difference.

The recursive formula for Euclid’s algorithm is:

• GCD(a, b) = GCD(b, a % b) where a % b is the remainder when a is divided by b.
• The base case is when b = 0, in which case GCD(a, b) = a.

This tutorial will guide you through creating a Python program that finds the GCD of two numbers using recursion.

Example:

• Function Name: gcd
• Function Purpose: Calculate the GCD of two numbers using recursion.
• Program Output:

  GCD of 48 and 18 is 6
  

Problem Statement

Create a Python program that:

• Defines a recursive function named gcd.
• The function takes two arguments, a and b.
• The function returns the GCD of a and b using recursion.
• The program calls the function with sample values to demonstrate its usage.

Solution Steps

1. Define the Recursive Function: Use the def keyword to define a function named gcd.
2. Add a Base Case: Include a base case to stop the recursion when b equals 0.
3. Implement the Recursive Case: In the recursive case, call the gcd function itself with b and a % b.
4. Call the Function: Call the gcd function with sample values, such as 48 and 18.
5. Display the Result: Print the result returned by the function.

Python Program

# Python Program to Find the GCD Using Recursion
# Author: https://www.rameshfadatare.com/

# Step 1: Define the recursive function
def gcd(a, b):
    # Step 2: Add a base case
    if b == 0:
        return a
    # Step 3: Implement the recursive case
    else:
        return gcd(b, a % b)

# Step 4: Call the function with sample values
result = gcd(48, 18)

# Step 5: Display the result
print(f"GCD of 48 and 18 is {result}")

Explanation

Step 1: Define the Recursive Function

• The function gcd is defined using the def keyword. It takes two parameters, a and b, which are the two numbers for which the GCD is to be calculated.

Step 2: Add a Base Case

• The base case checks if b is 0. If so, the function returns a because the GCD of any number and 0 is the number itself.

Step 3: Implement the Recursive Case

• If b is not 0, the function calls itself with the arguments b and a % b. This continues until b becomes 0, at which point the recursion stops.

Step 4: Call the Function

• The gcd function is called with the values 48 and 18. This initiates the recursive process to find the GCD.

Step 5: Display the Result

• The result of the function is stored in the result variable, and the print() function is used to display the GCD of 48 and 18.

Output Example

Example Output:

GCD of 48 and 18 is 6

Additional Examples

Example 1: GCD of Two Prime Numbers

# Calling the function to calculate the GCD of two prime numbers
result = gcd(17, 13)
print(f"GCD of 17 and 13 is {result}")

Output:

GCD of 17 and 13 is 1

Example 2: GCD of a Number and Itself

# Calling the function to calculate the GCD of a number and itself
result = gcd(24, 24)
print(f"GCD of 24 and 24 is {result}")

Output:

GCD of 24 and 24 is 24

Example 3: GCD of One Number Being 0

# Calling the function to calculate the GCD of a number and 0
result = gcd(9, 0)
print(f"GCD of 9 and 0 is {result}")

Output:

GCD of 9 and 0 is 9

Conclusion

This Python program demonstrates how to find the GCD of two numbers using recursion. The recursive implementation of Euclid’s algorithm is efficient and elegant, making it a popular choice for calculating the GCD. Understanding how to implement recursive functions and how to use them in solving mathematical problems is essential for mastering Python and other programming languages.