Link copied to clipboard. Share away!

Dismiss

Published on 09 Mar 2020

**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)
```

Output: 6

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[0] == 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.

If you have any feedback about this
article and want to improve this, please write to **enquiry@faceprep.in**

×