Latest Code Tutorials

Python Recursion: How to Use Recursion In Python

Python 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.

What is recursion in Python

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

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 Recursive Function

A recursive function is a function defined in terms of itself via self-referential expressions.

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.

Python Recursion Program

See the following program of Recursion in Python.


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

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

See the output.

➜  pyt python3
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 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 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!:

  1. 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)!
  2. 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

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

Disadvantages of Recursion

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

Finally, Python Recursion Example is over.

Recommended Posts

Python Operators

Python Not Equal Operator

Python sum()

Python Time sleep() Function

Python Data Types

1 Comment
  1. Amit Parmar says

    Thanks for the post

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.