Recursive Functions in Python

What is recursion?

Recursion is the process of repeating items or operations in a self-similar way.

In Python, if your program allows you to call a function inside the same function, then it is called a Recursive Function.

Recursion is an advanced and to some extent an unused topic. However, it is useful to know about this technique, as it allows you to deal with arbitrary structures and unpredictable shapes.

Example of Recursive Functions

Let’s calculate the factorial of a number in Python.

Ideally, you would do this by using a for loop.

Code

num = 5
factorial = 1

for i in range(1, num+1):
    factorial *= i

print(factorial)

Output

120

Pretty straightforward, right?

You can also do it using Recursion.

Code - Using Recursion

def factorial(x):

    if x == 1:
        return 1
    else:
        # call the function again
        return (x * factorial(x-1))

num = 5
print(factorial(num))

Output

120

When you call this function with a positive integer, it will keep calling itself recursively by decreasing the number.

Each function call multiplies the number with the factorial of the number until it is equal to one.

factorial(5)          # First function call
5 * factorial(4)      # 2nd function call with 4
5 * 4 * factorial(3)  # 3rd function call with 3
5 * 4 * 3 * factorial(2)  # 4th function call with 2
5 * 4 * 3 * 2 * factorial(1) # 5th function call with 1
5 * 4 * 3 * 2 * 1 
120

Basically, when the factorial() function returned 1, the recursion stopped. This is called Base Condition.

Every recursive function should have a base condition, otherwise, the recursion continues infinitely.

The Python interpreter limits the depths of recursion to help avoid infinite recursions. By default, the maximum depth of recursion is 1000. If the limit is crossed, it results in RecursionError.

Advantages of Recursion

1. Recursive functions look clean and elegant.
2. It can break down complex problems into multiple small problems using recursion.

Disadvantages of Recursion

1. Can be difficult to understand.
2. Recursion is expensive.
3. They are also hard to debug.