Python Recursion

What is Recursion?

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

Programmatically, when a function calls itself directly or indirectly, it is called recursion, and the corresponding function is called a recursive function.

The developer should be careful when using recursion as it can be pretty easy to slide into writing a function that never terminates or one that uses surplus amounts of processor power or memory.

However, when written correctly, recursion can be a cost-effective and mathematically elegant approach to programming.

Python Recursive Function

In Python, a function can call other functions. It is also possible for the function to call itself.

When a function calls itself, we called it a recursive function.

There are two main parts of a recursive function, the base condition and the recursive call. The base condition is essential because, without it, the function would repeat itself forever, causing a "stack overflow".

In the following illustration, we explain the working of a recursive function called my_recursive.

Example of a recursive function

In the following example, we will define a recursive function to calculate the factorial of an integer.

Factorial of a number is the multiplication of the number by every natural number below it until 1. For example, the factorial of 7 (denoted as 7!) is 1*2*3*4*5*6*7 = 5040

def fact(x):
    """A recursive function to 
     calculate the factorial of an integer"""

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


num = 4
print("The factorial of", num, "is", fact(num))

Output

The factorial of 4 is 24

As we can see above, the fact() function is a recursive function as it calls itself.

When the fact() function is called with a positive integer, it will recursively call itself by decreasing the number every time until it arrives to number one.

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

The call to the fact() recursive function can be explained in the following steps.

fact(4)                      # 1st call with 4
4 * fact(3)                # 2nd call with 3
4 * 3 * fact(2)          # 3rd call with 2
4 * 3 * 2 * fact(1)     # 4th call with 1
4 * 3 * 2 * 1              # return from 4th call as number = 1
4 * 3 * 2                   # return from 3rd call
4 * 3                         # return from 2nd call
4                               # return from 1st call 

The following illustration explains the steps of what is going during the call of the recursive fractional function.

As we can see above, the end of the recursion is when the number is equal to 1. This is called the base condition.

Every recursive function must have a base condition that will stop the recursion. If not, the function will call itself infinitely.

In Python, the interpreter limits the depths of recursion to avoid infinite recursions, resulting in stack overflows.

The default maximum depth of recursion is 1000. If the limit is passed, it will result in RecursionError.

In the following example, we will define a recursive function without the base condition to raise the RecursionError.

def my_recursor():
    my_recursor()

my_recursor()

Output

RecursionError   
      1 def my_recursor():
----> 2     my_recursor()
      3 
      4 my_recursor()

RecursionError: maximum recursion depth exceeded

Advantages of Using Recursion

There are several pros to use the recursion. The following list evokes some of them.

• Recursion can reduce time complexity.
• Recursion adds clarity and reduces the time needed to write and debug code.
• Sequence generation is easier using recursion than using some nested iteration.
• Recursion s better at tree traversal.

Disadvantages of Recursion

There are several cons to use the recursion. The following list evokes some of them.

• In some cases, the logic behind recursion is difficult to follow through.
• Recursion uses more memory.
• Recursion can be slow.
• Recursive function can be hard to debug.