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.
- Radha Krishna using Python Turtle
- Python Programming Examples | Fundamental Programs in Python
- Python | Delete object of a class
- Python | Modify properties of objects
- Python classmethod
- Python | Create a class that takes 2 parameters, print both parameters
- Python | Create a class, create an object of the class, access, and print property value
- Python | Find the maximum element in a list using lambda and reduce()
- Python | filter numbers(that are not divisible by 3 and 4) from a list using lambda and filter()
- Python | lambda function that returns the maximum of 2 numbers
- Python | Convert all strings of a list to uppercase using lambda
- Python | Square numbers of a list using lambda
- Python | Reverse and convert a string to uppercase using lambda
- Python | Convert String to uppercase using lambda
- Python | Reverse a list using lambda
- Python | Calculator using lambda
- Python | Square of a number using lambda
- Python | Multiply numbers using lambda
- Python | lambda with None
- Python | lambda with pass statement
- Python | Add numbers using lambda
- Python | Print Namaste using lambda
- Iterate over a string in Python
- Python | join() | Join list of strings
- Python | isalnum() method | check if a string consists only of alphabetical characters or numerical digits
- Python | isupper() and islower() methods to check if a string is in all uppercase or lowercase letters
- Python | count substring in a String | count() method
- Python | enumerate() on String | Get index and element
- Python | Convert a String to list using list() method
- Retrieve a module path in Python: 5 Methods