# 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-

siddharth@siddharth-Lenovo-Y520-15IKBN:~/python$ python3 gcd.py Enter First Number : 100 Enter Second Number : 50 GCD is : 50 siddharth@siddharth-Lenovo-Y520-15IKBN:~/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

You must be logged in to post a comment.