Recursion in Python is a process in which a function calls itself again and again until the given condition gets satisfied. Such a function which calls itself again and again is called a recursive function. Let us now understand how this works in detail.
Consider you need to print numbers in decreasing order starting from the given input number using recursion. Now, here is a sample input-output for your reference.
Input: 3 Output: 3 2 1
Here is how the below possible code for this program gets executed when recursion is involved.
def func(a):if(a == 0): returnelse: print(a) func(a - 1) #main() function func(3)
Now, consider the same above code where the function 'func' calls itself again and again without any end condition.
def func(a): print(a) func(a - 1) #main() function func(3)
Since the above code is not provided with any end condition, you may think that the output will be printed for infinite times. But, actually not. In Python, if the user does not provide any end condition, the process of recursion is restricted by some number as default. So in the output, the numbers will be printed from 3 to -994 with the errors saying
Traceback (most recent call last): File "main.py", line 5, in func(3) File "main.py", line 3, in func func(a - 1) File "main.py", line 3, in func func(a - 1) File "main.py", line 3, in func func(a - 1) [Previous line repeated 994 more times] File "main.py", line 2, in func print(a) RecursionError: maximum recursion depth exceeded while getting the str of an object
So whenever recursion is used in any program, the end condition is mandatory in that program.
Using recursion certain problems such as Towers of Hanoi, Depth First Traversal of a graph can be solved easily. If these concepts are implemented without using recursion, the number of lines of code will be large and the time taken to execute the code will be high.
Next, let us understand the working of recursion using simple examples.
Below are 4 example programs that use recursion to simplify the program.
The sum of the first three natural numbers can be calculated by adding the first three numbers this way - 1 + 2 + 3. Since the value 3 is small, it is easy to write manually or using loops. But, think of a larger value. In case of a large value, we can use a recursive function to do this task easily with fewer lines of code.
#program to find sum of 'n' natural numbers def sum(num):if(num != 0): return num + sum(num - 1) else: return 0 #main() function res = sum(3) print(res)
Here, Sum is a recursive function which calls itself until the value of 'num' becomes zero.
Similarly, the factorial of a number can be determined using recursion as shown below.
#factorial of a number using recursion def factorial(n):if n == 1: return n else: return n * factorial(n - 1) #main() function num = int(input("Enter a number: ")) if(num < 0): print("Sorry, factorial does not exist for negative numbers") elif(num == 0): print("The factorial of 0 is 1") else: print("The factorial of", num, "is", factorial(num))
Input from the user: 5 Output: Enter a number: 5 The factorial of 5 is 120
Also, we can use the process of recursion to find whether a string is a palindrome or not. Here is how you do it.
#string palindrome using recursion def palindrome(s):if len(s) < 1: return Trueelse: if s == s[-1]: return palindrome(s[1:-1]) else: return False #main() function a = str(input("Enter a string: ")) if(palindrome(a) == True): print("String is a palindrome") else: print("String is not a palindrome")
Input from the user: madam Output: Enter a string: madam String is a palindrome
Even a simple problem to find the Greatest Common Divisor (GCD) can be solved using recursion. Below is the code to find GCD of two numbers using the recursive method.
#GCD of two numbers def gcd(a,b):if(b == 0): return a else: return gcd(b, a % b) #main() function a = int(input("Enter the first number: ")) b = int(input("Enter the second number: ")) GCD = gcd(a,b) print("GCD is:", GCD)
Input from the user: 2 & 6 Output: Enter the first number: 2 Enter the second number: 6 GCD is: 2
1) what is recursion in python?
Recursion is a process of calling a function again and again until the given condition gets satisfied and such functions are called recursive functions.
2) Whether a condition is mandatory in a recursive function?
Yes, the end condition is mandatory in the recursive function. If the end condition is not mentioned, the interpreter throws an error.