Python – Recursion

In this tutorial, you will learn to create a recursive function (a function that calls itself).

What is recursion?

Recursion is the process of defining something in terms of itself.

Place two parallel mirrors facing each other in the physical world as an illustration. Any item between them would be recursively reflected.


Python Recursive Function

We know that a function in Python can call other functions. It’s possible that the function will call itself. Recursive functions are the name for these types of constructs.

The following image shows the working of a recursive function called recurse.

Python Recursive Function
Recursive Function in Python

A recursive function to find the factorial of an integer is shown below.

The product of all the integers from 1 to that number is the factororial of that number. The factorial of 6 (denoted as 6!) is 12345*6 = 720, for example.

Example of a recursive function

def factorial(x):
    """This is a recursive function
    to find the factorial of an integer"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("The factorial of", num, "is", factorial(num))

Output

The factorial of 3 is 6

factorial() is a recursive function in the previous example since it calls itself. Ad

This function will recursively call itself by decreasing the number if we call it with a positive integer.

Each function multiplies the integer by the factorial of the number immediately below it until it equals one. The instructions below will demonstrate how to make a recursive call.

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Let’s have a look at an illustration that depicts the process in detail:

Factorial by a recursive method
Working of a recursive factorial function

When the number is reduced to one, our recursion comes to an end. This is referred to as the “basic condition.”

If a recursive function does not provide a base condition that ends the recursion, the function will call itself indefinitely.

To avoid infinite recursions and stack overflows, the Python interpreter limits the depths of recursion.

The maximum depth of recursion is 1000 by default. If the limit is exceeded, RecursionError is thrown. Let’s take a look at one of these scenarios.

def recursor():
    recursor()
recursor()

Output

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Advantages of Recursion

  1. Recursion can be used to break down a complex function into smaller sub-problems.
  2. Recursion is more efficient than nested iteration for creating sequences.
  3. The use of recursive functions makes the code appear simple and efficient.

Disadvantages of Recursion

  1. Recursive calls consume a lot of memory and time, making it inefficient to use.
  2. Debugging recursive functions is difficult.
  3. The logic of recursion can be difficult to comprehend at times.

Leave a Comment

Your email address will not be published.