Gcd using recursion in python

This is a Python Program to find the GCD of two numbers using recursion.

Problem Description

The program takes two numbers and finds the GCD of two numbers using recursion.

Problem Solution

1. Take two numbers from the user.
2. Pass the two numbers as arguments to a recursive function.
3. When the second number becomes 0, return the first number.
4. Else recursively call the function with the arguments as the second number and the remainder when the first number is divided by the second number.
5. Return the first number which is the GCD of the two numbers.
6. Print the GCD.
7. Exit.

Program/Source Code

Here is source code of the Python Program to find the GCD of two numbers using recursion. The program output is also shown below.

def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))
GCD=gcd(a,b)
print("GCD is: ")
print(GCD)

Program Explanation

1. User must enter two numbers.
2. The two numbers are passed as arguments to a recursive function.
3. When the second number becomes 0, the first number is returned.
4. Else the function is recursively called with the arguments as the second number and the remainder when the first number is divided by the second number.
5. The first number is then returned which is the GCD of the two numbers.
6. The GCD is then printed.

Runtime Test Cases

 
Case 1:
Enter first number:5
Enter second number:15
GCD is: 
5
 
Case 2:
Enter first number:30
Enter second number:12
GCD is: 
6

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Next Steps:

• Get Free Certificate of Merit in Python Programming
• Participate in Python Programming Certification Contest
• Become a Top Ranker in Python Programming
• Take Python Programming Tests
• Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10