Python Recursion: The Complete Guide

Recursion is the method of programming or coding the problem, in which the function calls itself one or more times in its body. Usually, it is returning a return value of this function call. If the function definition satisfies the condition of recursion, we call this function a recursive function.

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

Python recursion

Python recursion is a common mathematical and programming concept in which a function calls itself. A recursive function is a function defined in terms of itself via self-referential expressions. This has the benefit of meaning that you can loop through data to reach a result.

The recursive function has to fulfill an essential condition to be used in a program: it has to terminate. The recursive function terminates if with every recursive call the solution of the problem is downsized and moves towards the base case.

The base case is a case where a problem can be solved without further recursion. The recursion can end up in an infinite loop if the base case is not met in the calls.

Factorial of any number is the product of all the integers from 1 to that number. For instance, the factorial of 6 (denoted as 6!) is 1*2*3*4*5* = 120.

A Real-world example would be to place two parallel mirrors facing each other like the movie in inception. Any object in between them would be reflected recursively and you will see infinite reflections of that object.

Python Recursion Program

See the following program of Recursion in Python.

# app.py

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


number = 5
print("The factorial of", number, "is", factorial(number))

See the output.

➜  pyt python3 app.py
The factorial of 5 is 120
➜  pyt

In the above example, factorial() is the recursive function as it calls itself.

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

Each function calls multiples the number with the factorial of number 1 until the number is equal to one.

What is the base case in recursion?

When working with recursion, we should define the base case for which we already know an answer. In the above example, we are finding the factorial of the integer number, and we already know that the factorial of 1 is 1 so this is our base case.

Each successive recursive call to a function should bring it closer to the base case, which is precisely what we are doing in the above example.

We use a base case in a recursive function so that the function stops calling itself when the base case is reached. Without the base case, the function would keep calling itself indefinitely.

Python Recursion Example

To demonstrate this structure, let’s write the recursive function for calculating n!:

Decompose the original problem into more straightforward instances of the same problem. This is the recursive case:
```
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1
n! = n x (n−1)!
```

As a large problem, we need to broke down into successively less complex ones, those subproblems must eventually become so simple that they could be solved without any further subdivision. This is the base case:

n! = n x (n−1)! 
n! = n x (n−1) x (n−2)!
n! = n x (n−1) x (n−2) x (n−3)!
⋅
⋅
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3!
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2!
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!

Here, 1! is our base case, and it equals 1.

Advantages of Recursion

Recursive functions make code look clean and elegant.
The complex task can be broken down into simpler sub-problems using recursion.
Sequence generation is more comfortable with recursion than using the nested iteration.

Disadvantages of Recursion

The logic behind recursion is hard to follow.
The recursive calls are expensive (inefficient) as they take up a lot of memory and time.
Recursive functions are very hard to debug.

That’s it for this tutorial.