Find the GCD of two numbers recursively in Python

By Siddharth Shankar Debata

In this tutorial, we will learn to find the GCD of two numbers recursively in Python language. Here, we will find the Greatest Common Divisor (GCD) using a user-defined recursive function. A recursive function is a function which calls itself based on a condition. If you are looking for a Python program which calculates the GCD using a recursive function, you are at the right place.

Calculate Greatest Common Divisor of two numbers

The GCD of two numbers is the largest possible number which divides both the numbers. Here we will calculate this largest possible number using a recursive function. So, to calculate GCD follow the steps below-

• Input the two numbers num1 and num2 from the user.
• Call the recursive function and pass these two numbers.
• Now, check the value of num2.
• If num2 is equal to 0, then return num1 to the calling function.
• Otherwise, calculate the remainder by dividing num1 and num2.
• Call the recursive function again and pass the variables num2 and result of the above step.
• Finally, the GCD of the two numbers is returned by the first call of the recursive function.

To understand these steps in a better way, let us take an example-

num1 = 10
num2 = 20
GCD = call func(10,20)
            num2 = 20 > 0
            num1 % num2 = 10
            call func(20,10)
                  num2 = 10 > 0
                  num1 % num2 = 0
                  call func(10,0)
                        num2 = 0 = 0
                        return 10
                  return 10
            return 10 
GCD = 10

So, the last recursive function call returns the final result to the calling function. The result is finally returned by the first call of the recursive function. Finally, we get the GCD of 10 and 20 i.e. 10 as a result.

Finding GCD of two numbers using a recursive function in Python

Firstly, we take input from the user. We define a function ‘calc_gcd’ which recursively calculates the GCD and returns the final result. Finally, we store the GCD in the variable ‘result’. The Python program is given below-

def calc_gcd(num1,num2):
    if(num2 == 0):
        return num1
    else:
        return calc_gcd(num2,num1%num2)

num1 = int(input("Enter First Number : "))
num2 = int(input("Enter Second Number : "))
result = calc_gcd(num1,num2)
print("GCD is : {}".format(result))

Python program output

The above Python program displays the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two numbers recursively. So the output after sample execution is as follows-

[email protected]:~/python$ python3 gcd.py
Enter First Number : 100
Enter Second Number : 50
GCD is : 50
[email protected]:~/python$

Finally, we get the GCD of two numbers 100 and 50 as 50. So, we can find the GCD of any two numbers using the above Python program.

Thank you for reading this tutorial and I hope it is useful to you.