**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.

**How Does Recursion Work in Python**

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:3Output:

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):

return

else:

print(a)

func(a - 1)

#main() function

func(3)

**Explanation:**

**How Many Times will a Recursive Function be called?**

**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.

**Examples on Recursion in Python**

Below are 4 example programs that use recursion to simplify the program.

**a) Sum of ‘n’ natural numbers using recursion in Python**

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.

**b) Factorial using recursion in python**

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:5Output:

Enter a number: 5

The factorial of 5 is 120

**c) Palindrome using recursion in python**

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 True

else:

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:madamOutput:

Enter a string: madam

String is a palindrome

**d) GCD using recursion in python**

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 & 6Output:

Enter the first number: 2

Enter the second number: 6

GCD is: 2

**Recursion FAQS**

Recursion is a process of calling a function again and again until the given condition gets satisfied and such functions are called recursive functions.

Yes, the end condition is mandatory in the recursive function. If the end condition is not mentioned, the interpreter throws an error.