Find the GCD of two numbers recursively in Python
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.
Leave a Reply