Python Recursion

Introduction to Python recursion

In this article, we will discuss the recursion concept in Python. In general, recursion simply means a function that is defined can call itself. This concept is common in all programming languages and Python; we know that one defined function can call another function; similarly, a defined function can call itself to loop through the given data until a certain condition provides the output or stops the loop. But if this recursion process of calling itself is not stopped by any condition, then the loop will go into an infinity loop, which may sometimes lead to occupy more memory, or the program never terminates, and there will be no output.

Working of Recursion in Python

In Python, defining something in terms of itself or a function to call itself or, in simple words executing the same piece of code again and again for some new values such process is known as recursion. Therefore, we will see how recursion works where; the recursion function is called by some external piece of code in the program. The recursion function is a function that calls itself until a certain condition is satisfied. Hence, we should be very careful as recursion is a very efficient and elegant approach in programming. Still, we have to properly set the condition criteria; recursion may lead to an infinite loop which can cause a program to never terminate or use excess memory and processor power.

Examples of Python Recursion

Now let us demonstrate how the recursive function works with examples as we discussed in the above section.

Example #1

Code:

print("Program to demonstrate recursion in Python")
def rcur_func(x):
    if(x>=1):
        rcur_func(x-1)
        print(x)
print("The output of the above recursion function is as follows:")
rcur_func(5)

Output:

In the above program, we can see we have defined a function “rcur_func()” to this function, we are passing an integer variable “x”, and then we are checking for the condition using “if” statement such as if (x >= 1 ) and if the condition is satisfied, then it enters the if loop and where it calls the same function again and passes the argument by decrementing the x value by 1 ( x-1 ). Therefore, in the above program, we have passed the x value as  “5” to the defined function. Now when 5 is given to the “if” statement, then the condition is satisfied and hence the if loop results “true”, and it enters the loop. Again the same function is called by passing the decremented by 1 x value ( x =5 -1 ), now the x value is 4 again it will be checked by the “if” statement and the “if” loop condition is satisfied and results “true” and enters the loop, and again the function is called by passing the decremented by 1 x value ( x= 4 – 1). This process is continued until the if statement condition results false, that means until the x value reaches 1. Then the output will print the values of the above recursion as 1, 2, 3, 4, 5, as shown in the above screenshot. It will print only till 5 as the integer value passed to the recursion function is 5, and if we pass integer value 9, then it will print till 9.

Now let us see what the termination condition in the recursion concept is. In Python, as we discussed above, it is very important for a recursive function to have a termination condition because if the condition is not specified, then it may lead to infinite loop recursion, which never terminates the program. Therefore the recursion function needs to have a termination condition. Now let us take a famous example of finding the factorial of the given number.

So to find the factorial of a given number “z”, we calculate it as z = z * (z -1) until z is greater than 1, we need to compute this expression, and if z = 0, then the above factorial expression will result in 1. So let us demonstrate programmatically in the below example.

Example #2

Code:

print("Program to demonstrate recursion termination condition in factorial of number")
def factorial_func(z):    
    if z == 1:
        print(z)
        return 1    
    else:
        print (z,'*', end=' ')
        return (z * factorial_func(z-1))
z = 5
print("The factorial of the given number", z," is as follows:")
print(factorial_func(z))

Output:

In the above program, we can see how we have calculated the factorial of the given number 5, and the result is as displayed in the above screenshot.

In Python, there is a recursion limit; unlike in other programming languages, we can create an infinite loop. So to check the recursion limit in the Python program, we have to use the sys module. In Python, if we are trying to calculate the above factorial function by passing the value of z as 3000, then it will give us a runtime error or RecursionError saying “maximum recursion depth is exceeded” because in Python, by default, the recursion function call stops after 1000 and to change this limit we have to use “setrecursionlimit()” of sys module to the desired value. Now let us demonstrate this in the below example.

Example #3

Code:

def factorial_func(z):    
    if z == 1:
        print(z)
        return 1    
    else:
        print (z,'*', end=' ')
        return (z * factorial_func(z-1))

z = 2000
print("The factorial of the given number", z," is as follows:")
print(factorial_func(z))

Output:

So we can avoid the above problem by using the sys module with setrecursionlimit() in the below program.

Code:

import sys
sys.setrecursionlimit(3000)

def factorial_func(z):    
    if z == 1:
        print(z)
        return 1    
    else:
        print (z,'*', end=' ')
        return (z * factorial_func(z-1))

z = 2000
print("The factorial of the given number", z," is as follows:")
print(factorial_func(z))

Output:

So we can get the output to the factorial of 2000 by setting the recursion limit by 3000 using the sys module’s function setrecursionlimit().

Conclusion

In this article, we defined the recursion concept in Python, which defines something in terms of itself or simple words calling the same piece of code; again and again, such process is known as recursion is known as recursive functions. In this article, we saw an example of recursion. Then we saw why the termination condition is important in the recursion concept to avoid an infinite loop that never gets terminated. In this, we also saw about the recursion limit in Python, which is set using the sys module’s function setrecursionlimit() function; if we do not use then, it may lead to RecursionError.

Recommended Articles

This is a guide to Python Recursion. Here we discuss the Working and How the Recursive Function of Python works with examples. You may also have a look at the following articles to learn more –

1. Python Dump
2. Python Unicode Error
3. Python Function Generator
4. Python File readline