w3resource

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


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:

Flowchart: Recursion: gcd of two integers.

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.

Go to:


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

Python Code Editor:

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.