Python Recursive Function

In this section, you will learn Python recursive function.

What is Python Recursive Function

A recursive function is a function that calls itself and this process is called function recursion.

For example, let’s calculate the factorial of a number, for example, 6.

6 * 5 * 4 * 3 * 2 * 1

In the following code, a recursive function is created which finds the factorial of a number:

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return (n * fact(n - 1))
a = 6
print("Factorial of", a, "=", fact(a))

Factorial of 6 = 720

The function fact(n) is a recursive function. The fact function calls itself with argument n-1 till the number becomes 1 and this is how factorial is calculated, that is multiplying the number by the factorial of one less than the number.

In this recursive function, there is a base condition that is when the number becomes 1, 1 is returned and in this way recursive call becomes finite.

When creating a recursive function, there must be a base condition to end that recursive call.

Limitation of Recursion:

As you have noticed, every time when the function calls itself, it needs some memory to store some intermediate values. Therefore recursive function consumes much more memory than a normal non-recursive function. Python sets the recursion calls limitation to 3000.

>>> import sys
>>> sys.getrecursionlimit()
3000

It raises a RecursionError if recursion exceeds 3000.

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return (n * fact(n - 1))
    
print(fact(4000))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Solution to Remove Recursion Limitation

You could solve the recursion limitation by setting the recursion limitation to a number larger than the required recursion.

import sys
sys.setrecursionlimit(5000)
def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return (n * fact(n - 1))
    
print(fact(4000))

Advantage of Recursion:

• Using recursive functions, the problem can be divided into sub problem which can be solved easily.
• The code becomes neat and clean.

Disadvantage of Recursion:

• It is sometimes difficult to follow through the logic of recursive function.
• To solve each sub problem will take a lot of time so recursive functions are inefficient.