Hello friends and welcome to our website copyassignment.com. In this tutorial, we are going to learn a simple program of GCD Recursion in Python. Until now, we have covered various topics of python from basic to advanced projects, and have shared a number of tutorials for that. Here we going to study the different ways to find GCD recursion in Python and get a basic idea of it.
What is GCD?
A GCD or Greatest Common Divisor of two integers or more integers is the largest positive integer that allows the dividing of both numbers without leaving any remainder.
Example: To find GCD of 54 and 24
All divisors of 54 are 1, 2, 3, 6, 9, 18, 27, 54
All divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24
Common divisors of 54 and 24 are 1, 2, 3, 6
gcd(54,24) is 6 i.e. greatest common divisor of 54 and 24 is 6.
GCD Recursion method
A GCD recursion method is a method of tail recursion. A tail recursion means, the last thing a method does is to call itself. The tail recursion and the iteration in the program enable us to repeat a compound statement.
Let us understand the python program of GCD Recursion in detail
Python program for GCD of two numbers using Recursion
Method1 for GCD using Recursion in Python
#Define the function gcsd def gcd(a,b): if(b==0): return a else: return gcd(b,a%b) #Takes the input values in a and b a=int(input("Enter first number:")) b=int(input("Enter second number:")) #output of the gcd function output =gcd(a,b) print("Greatest Common Divisor is: ") print(output)
Let us understand the code of the Python Program of GCD Recursion line by line:
- We have defined a function gcd(a,b) in which we can take 2 parameters in a and b.
- We have defined the if block in which if the value of b==0 then the output is the value of a. else the function is recursively called with the arguments as the second number and the remainder, as the first number is divided by the second number.
- “a” and “b” are variables that take the input numbers.
- The “output” variable takes the output returned.
- The print function prints the statement and the output.
Method2 for GCD Recursion Python
def gcd(a, b): if a == b: return a elif a < b: return gcd(b, a) else: return gcd(b, a - b) #Defined the values of a and b a = 20 b = 4 print(gcd(a, b))
- In the method, we have defined function gcd which takes 2 parameters a,b.
- Here we have used the if-else block where in the if block we check if a==b i.e if both a and b values are the same then it will return the value a, else if a<b then it calls gcd(b, a) else when both the conditions become false it will recursively call the gcd(b,a-b) function till we get the output
- .Here we have defined the values of a and b as 20 and 4 respectively.
- Print(gcd(a,b)) prints the output of the function.
Hence, we have discussed two methods to calculate GCD Recursion using Python programming language.
For more articles on python keep visiting our site.
Thank you for reading this article.
- Sequel Programming Languages(SQL)
- Run Python Code, Install Libraries, Create a Virtual Environment | VS Code
- Calendar using Java with best examples
- How to make a Process Monitor in Python?
- C++ Array Assignment
- Employee Management System Project in Java
- Shift Numbers in Python | Assignment Expert
- Sum of n numbers in Python using for loop
- NxNxN Matrix in Python 3
- Calculator Program in Python | On Different IDEs
- Naive Bayes in Machine Learning
- Lee Algorithm in Python | Solution to Maze Routing Problem in Python
- Miles Per Gallon Python Program
- Automate Data Mining With Python
- Create and Print a List of Prime Numbers in Python
- Support Vector Machine(SVM) in Machine Learning
- Python Increment By 1
- Vending Machine with Python Code
- Python Turtle Shapes- Square, Rectangle, Circle
- Python OOP Projects | Source code and example
- Happy Birthday In Binary Code
- AES in Python | Encrypt & Decrypt | PyCryptodome
- Make Minecraft in Python
- Battleship Game Code in Python
- Convert ipynb to Python
- Simple Atm Program in Python
- Python – Sort All Words In a File And Put It In A List – 3 Easy Method
- Python Docstring Generator | PyCharm and VsCode
- Format Numbers as Currency with Python: 3 Easy Methods
- MD5 Hash in Python