Python Recursion (Everything you should know)

In this Python tutorial, we will discuss recursion in python. Also, we will see these below topics as:

  • What is recursion in python?
  • Recursive function in python
  • Python recursion examples
  • Python recursion Fibonacci
  • Python get the current value of the recursion limit
  • Python change the maximum recursion depth
  • Python recursion list
  • Recursion Error: maximum recursion depth exceeded in comparison python
  • Python recursion advantages
  • Python recursion disadvantage

What is recursion in python?

What is recursion in python? A function that calls itself is a recursive function in Python. Recursion is used when a certain problem is defined in terms of itself. This has the benefits that you can loop through the data to reach a result. Also, recursion can lead to an infinite loop, if the base case is not met in the calls. The recursive approach provides a very concise solution to a complex problem.

Recursive function in python

In python, as we know that a function can call other functions. It is also possible that a function can call itself. These types are termed recursive functions.

We can take the example of factorial for a recursive function to understand it better.

Example:

def factorial(number):
    if number == 1:
        return 1
    else:
        return(number * factorial(number - 1))
number = 4
print("Factorial of", number, "is: ", factorial(number))

After writing the above code (recursive function in python), Ones you will print “ number ” then the output will appear as “ Factorial of 4 is: 24 “. In this example, we are defining a user-defined function factorial(). This function finds the factorial of a number by calling itself repeatedly until it reaches ” 1 ” which is the base case.

You can refer to the below screenshot for recursive function in python

Recursive function in python
Recursive function in python

Python recursion advantages

  1. The main benefit of a recursive approach in Python is that it allows programmers to take advantage of the repetitive structure present in problems.
  2. Recursion makes our program easier to write.
  3. Complex case analysis and nested loops can be avoided.
  4. Recursion makes code more readable and efficient.

Python recursion disadvantage

  1. Not all problems can be solved using recursion.
  2. It slows down the execution time and calling to a recursive function is not memory efficient.
  3. If you don’t define the base case then the code will run indefinitely
  4. Debugging is difficult in recursive function as the function call itself in a loop.

Python recursion examples

We will be doing the example of recursion in Python, to calculate the sum of n natural numbers. By defining the function ” def sum(number) “.

Example:

def sum(number):
    if number == 1:
        return 1
    else:
        return(number + sum(number - 1))
number = 6
print("Sum of", number, "is: ", sum(number))

After writing the above code (python recursion examples), Ones you will print “ number ” then the output will appear as “ Sum of 6 is: 21 “. In this example, we are defining a user-defined function sum(). This function finds the sum of a number by calling itself repeatedly until it reaches ” 1 ” which is the base case.

You can refer to the below screenshot for python recursion examples

Python recursion examples
Python recursion examples

Python recursion Fibonacci

A Fibonacci sequence is a sequence of integers in which the first two terms will be 0 and 1 and all other terms of the sequence are obtained by adding their preceding two terms.

A recursion_fib() function is used to calculate the n_term of sequence.

Example:

def recursion_fib(num):
   if num <= 1:
       return num
   else:
       return(recursion_fib(num-1) + recursion_fib(num-2))
n_term = 5
if n_term <= 0:
   print("Please enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(n_term):
       print(recursion_fib(i))

After writing the above code (python recursion fibonacci), Ones you will print “recursion_fib(i)” then the output will appear as “ 0 1 1 2 3 “. In this example, we are recursively calling the function and the loop is used to iterate and calculate each term recursively.

You can refer to the below screenshot for python recursion fibonacci

Python recursion Fibonacci
Python recursion Fibonacci

Python get current value of the recursion limit

To get the current value of the recursion limit in Python, we will import sys module, and then we will use “sys.getrecursionlimit()” to get the current recursion limit.

Example:

import sys
print("The current value of the recursion limit:")
print(sys.getrecursionlimit())

After writing the above code (python get current value of the recursion limit), Ones you will print “sys.getrecursionlimit()” then the output will appear as “ 1000 “ which is the default value. In this example, we are getting the current value of the recursion limit by using sys.getrecursionlimit().

You can refer to the below screenshot get current value of the recursion limit

Python get current value of the recursion limit
Python get current value of the recursion limit

Python change the maximum recursion depth

To change the maximum recursion depth in Python, we will use “sys.setrecursionlimit()” which will increase the recursion limit and we can perform successive operations recursively.

Example:

import sys
sys.setrecursionlimit(1006)
new_limit = sys.getrecursionlimit()
print(new_limit)

After writing the above code (python change the maximum recursion depth), Ones you will print “new_limit” then the output will appear as “ 1006 “. In this example, we are getting the changed value of the recursion limit by using sys.setrecursionlimit(1006).

You can refer to the below screenshot python change the maximum recursion depth

Python change the maximum recursion depth
Python change the maximum recursion depth

Python recursion list

We will perform the sum of a list using recursion in Python, to calculate the sum of the given list first define the function ” def sum(list) “. When the base condition is met, the recursion will come to an end and it will return the sum of a list.

Example:

def sum(list):
    if len(list)==0:
       return 0
    else:
       return list[0]+sum(list[1:])
list = [1,2,3,4,5]
print(sum(list))

After writing the above code (python recursion list), Ones you will print “sum(list)” then the output will appear as “ 15 “. In this example, we are getting the sum of the list by calling the sum function, where it adds all elements recursively until it met the base condition which is “0”.

You can refer to the below screenshot python recursion list

Python recursion list
Python recursion list

Recursion Error: maximum recursion depth exceeded in comparison python

The recursive function includes limits to ensure that they do not execute infinitely. When given a large input, the program crashes and gives the error “maximum recursion depth exceeded”. This means that the function should run until a particular condition is met.

Example:

def fact(num):
    if num == 0:
        return 1
    else:
        return num * fact(num-1)
print(fact(2000))

After writing the above code, Once you will print “(fact(2000))” then the error will appear as a “RecursionError: maximum recursion depth exceeded in comparison”. Here, the error will occur if you write a recursive function that executes more than a particular number of iterations (usually998), then you will get this error.

You can see the below screenshot maximum recursion depth exceeded in comparison python

Recursion Error: maximum recursion depth exceeded in comparison python
Recursion Error: maximum recursion depth exceeded in comparison python

Python has raised a recursion error to protect against a stack overflow. To solve this error we can increase the recursion limit in our program by using the “setrecursionlimit(4000)” method, and now the program is executed without errors.

Example:

import sys
sys.setrecursionlimit(4000)
def fact(num):
    if num == 0:
        return 1
    else:
        return num * fact(num-1)
print(fact(2000))

After writing the above code, Once you will print “(fact(2000))” then the output will appear without any error. Here, the error is resolved by using the import sys module and changing the recursion limit by using setrecursionlimit(). Now we can see that the recursion limit is increased.

You can refer to the below screenshot for the output

maximum recursion depth exceeded in comparison python
maximum recursion depth exceeded in comparison python

You may like the following Python tutorial:

In this tutorial we have learned bout recursion in python. Also we have covered these topics.

  • What is recursion in python?
  • Recursive function in python
  • Python recursion examples
  • Python recursion Fibonacci
  • Python get the current value of the recursion limit
  • Python change the maximum recursion depth
  • Python recursion list
  • Recursion Error: maximum recursion depth exceeded in comparison python
  • Python recursion advantages
  • Python recursion disadvantage