Python Data Structures and Algorithms - Recursion: gcd of two integers

Last update on March 27 2025 12:50:24 (UTC/GMT +8 hours)

11. Greatest Common Divisor (GCD) Using Recursion

Write a Python program to find the greatest common divisor (GCD) of two integers using recursion.

Sample Solution:

Python Code:

# Define a function named Recurgcd that calculates the greatest common divisor (GCD)
# of two numbers 'a' and 'b' using recursion and the Euclidean algorithm
def Recurgcd(a, b):
    # Determine the lower and higher values between 'a' and 'b'
    low = min(a, b)
    high = max(a, b)

    # Check if the lower value is 0 (base case for GCD calculation)
    if low == 0:
        # If the lower value is 0, return the higher value (GCD is the non-zero value)
        return high
    # Check if the lower value is 1 (base case for GCD calculation)
    elif low == 1:
        # If the lower value is 1, return 1 (GCD of any number with 1 is 1)
        return 1
    else:
        # If neither base case is met, recursively call the Recurgcd function
        # with the lower value and the remainder of the higher value divided by the lower value
        return Recurgcd(low, high % low)

# Print the result of calling the Recurgcd function with the input values 12 and 14
print(Recurgcd(12, 14))

Sample Output:

2

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to recursively compute the GCD of two integers using Euclid's algorithm.
• Write a Python program to implement a recursive function that returns the greatest common divisor and handles negative inputs.
• Write a Python program to use recursion to calculate the GCD and then compute the LCM of two numbers.
• Write a Python program to implement the subtraction-based method for finding the GCD recursively.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to calculate the value of 'a' to the power 'b'.
Next: Python Math Exercise Home.