Recursion in Python

Recursion is the act of calling a function from the same function. The functions which perform recursion are known as Recursive functions. Python uses the concept of recursion to simplify the codes. Basically, recursion follows the idea of breaking a big problem into smaller and less complex problems.

How does recursion work?

A recursive function has two cases: Recursive case & Base case. 

  • The recursive case keeps on calling the function again and again until the base case is executed.
  • The actual calculations are done only in the base case.

Example of Recursion

The best and most common example of recursion is factorial. Factorial of a number N is the product of numbers from N to 1 i.e N! = N * N-1 * N-2... * 3 * 2 * 1. To solve this problem with recursion, what you need to do is:

factorial of N = N * factorial of (N-1)

Assume N = 5,
Then 5! = 5 * 4!

Let us create the program for the above example.

def find_fact(n): #function definition
    if n==0: #base case
        return 0
    elif n==1: #base case
        return 1
    else:
        return (n * find_fact(n-1)) #recursive case

f = int(input('Please enter a number to calculate its factorial.'))
print('Factorial of', f, ' =', find_fact(f)) #function call

Explanation:

  • In the above program, a function find_fact() is created which takes one parameter i.e n. Inside this function, we have an elif condition.
  • The first condition says, if n=0, the function will return 0 to the caller.
  • The second condition says, if n=1, then the function will return 1 to the caller.
  • Since these two conditions are generating and returning certain value to the caller, they are identified as the base case.
  • Now comes the else part, which is the recursive case because it is calling the find_fact() function again. The value returned to this call is multiplied by n.
  • This process keeps on repeating until the base case is reached, i.e when n=1.
  • Finally, the product (n * find_fact(n-1)) is the actual result.

Output:

Please enter a number to calculate its factorial.1
Factorial of 0 = 0

Please enter a number to calculate its factorial.1
Factorial of 1 = 1

Please enter a number to calculate its factorial.1
Factorial of 5 = 120

Limit of Recursion

By limit of recursion, we mean the maximum number of times the recursion can occur. It is possible that a recursive function continues to call itself forever, for example:

def infinite(): #function definition
    print(a)
    infinite() #recursive call
infinite() #function call

The function infinite() has no such condition that stops the recursive call, so the code will run endlessly.

Try running the above program, you will find that the interpreter will stop the process after a number of recursions and an error will be raised.

Output: error

RecursionError: maximum recursion depth exceeded while pickling an object

This happens because the python interpreter has already set a limit for recursion which 1000. Thus a function can call itself for only 1000 times.

This limit is set to prevent hanging of the system. You can also check the limit of your interpreter with the help of the function getrecursionlimit().

Before using this function, you need to import the sys module.

import sys
print(sys.getrecursionlimit())

Output:

1000

How to change the recursion limit?

Python allows you to change its default recursion limit as per the requirement of your program with the help of the function setrecursionlimit().

The required limit is passed as the argument to this function.

import sys
sys.setrecursionlimit(4000)
print('new limit= ', sys.getrecursionlimit())

Output:

new limit= 4000