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: 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):
        return 
    else:
        print(a)
        func(a - 1)
        
#main() function
func(3)
Explanation:

recursion in python

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