Python Tutorial - Recursive Function

1. What Is Python Recursive Function
2. Limitation of Recursion
3. Advantage of Recursion
4. Disadvantage of Recursion

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.