Python Recursive Function
In this section, you will learn Python recursive function.
What is Python Recursive Function
A recursive function is a function that calls itself and this process is called function recursion.
For example, let’s calculate the factorial of a number, for example, 6.
6 * 5 * 4 * 3 * 2 * 1
In the following code, a recursive function is created which finds the factorial of a number:
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return (n * fact(n - 1))
a = 6
print("Factorial of", a, "=", fact(a))
Factorial of 6 = 720
The function fact(n) is a recursive function. The fact function calls itself with argument n-1 till the number becomes 1 and this is how factorial is calculated, that is multiplying the number by the factorial of one less than the number.
In this recursive function, there is a base condition that is when the number becomes 1, 1 is returned and in this way recursive call becomes finite.
When creating a recursive function, there must be a base condition to end that recursive call.
Limitation of Recursion:
As you have noticed, every time when the function calls itself, it needs some memory to store some intermediate values. Therefore recursive function consumes much more memory than a normal non-recursive function. Python sets the recursion calls limitation to 3000.
>>> import sys
>>> sys.getrecursionlimit()
3000
It raises a RecursionError if recursion exceeds 3000.
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return (n * fact(n - 1))
print(fact(4000))
Traceback (most recent call last):
File "<pyshell#2>", line 1, in <module>
print(factorial(4000))
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
[Previous line repeated 989 more times]
File "<pyshell#1>", line 2, in factorial
if n == 1:
RecursionError: maximum recursion depth exceeded in comparison
Solution to Remove Recursion Limitation
You could solve the recursion limitation by setting the recursion limitation to a number larger than the required recursion.
import sys
sys.setrecursionlimit(5000)
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return (n * fact(n - 1))
print(fact(4000))
Advantage of Recursion:
- Using recursive functions, the problem can be divided into sub problem which can be solved easily.
- The code becomes neat and clean.
Disadvantage of Recursion:
- It is sometimes difficult to follow through the logic of recursive function.
- To solve each sub problem will take a lot of time so recursive functions are inefficient.
