# Recursion in Python | Recursion with Examples

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:321`

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() functionfunc(3)`

## 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 numbersdef sum(num):    if(num != 0):        return num + sum(num - 1)    else:        return 0#main() functionres = 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 recursiondef factorial(n):    if n == 1:        return n    else:        return n * factorial(n - 1) #main() functionnum = 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: 5The 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 recursiondef palindrome(s):    if len(s) < 1:        return True    else:        if s[0] == s[-1]:            return palindrome(s[1:-1])        else:            return False#main() functiona = 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: madamString 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 numbersdef gcd(a,b):    if(b == 0):        return a    else:        return gcd(b, a % b) #main() functiona = 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: 2Enter the second number: 6GCD 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.