In this article, you will be learning how to create a recursion python (recursive function), what are its advantages and disadvantages along with examples for each.
What is Recursion?
Recursion is the process in which the function calls itself, the call may be direct or indirect. Using recursion, certain problems like Towers of Hanoi, DFS of graphs etc can be solved easily.
The most well known physical world example of recursion is infinite images formed by two parallel mirrors. The image formed acts as an object and form a new image this way the process is defined in terms of itself and hence shows recursion.
Python Recursive Function
Any function which calls itself directly or indirectly is called a python recursive function.
Example: In the recursive_function() below, the function is calling itself inside its definition.
def recursive_function():
# base condition and rest of the code
# recursive call
recursive_function()
Example: A Fibonacci sequence is an integer sequence that goes like 0, 1, 1, 2, 3, 5, 8…
Let’s write a recursive code to find the Fibonacci sequence for n terms.
Code
# Code to print the Fibonacci sequence up to n terms
# Recursive Fibonacci function
def recursive_fibonacci(n):
if n <= 1:
return n
else:
return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))
n_terms = 8
# check if the number of terms is valid
if n_terms <= 0:
print(“Invalid input ! Input must be a positive value”)
else:
print(“Fibonacci series is :”)
for i in range(n_terms):
print(recursive_fibonacci(i))
Output
Fibonacci series is :
0
1
1
2
3
5
8
13
Explanation
In the above example, we are calling the function recursive_fibonacci with a positive integer and it is recursively calling itself by breaking the problem into subproblems.
Like when we are finding the 5th term of Fibonacci series that is n=4, here is what happened:
recursive_fibonaci(4) #first call will be made with n=4
recursive_fibonaci(3) + recursive_fibonaci(2) # second call will be made with n=3 and n=2
[recursive_fibonaci(2)+recursive_fibonaci(1)]+[recursive_fibonaci(1)+recursive_fibonaci(0)]
[recursive_fibonaci(2) + 1] + [1 + 0] # as we return n for n<=1
[recursive_fibonaci(1)+recursive_fibonaci(0)+1] +[1]
[1 + 0 + 1] + [1]
2 + 1
3
Hence the 5th term of the fibonacci series is 3.
One thing to observe from the example above is that our recursion ends when the number is 1 or less than 1. This is called the base condition of recursion, where our function stops calling itself. If there is no base condition then our recursive function will run infinite times and hence will cross the limits of depths of recursion resulting in stack overflows. If the limit of recursion depth is crossed, that is 1000 by default, it results in RecursionError.
Example:
def infinite_recursion():
infinite_recursion()
infinite_recursion()
Output
Traceback (most recent call last):
File “program.pys3”, line 3, in <module>
infinite_recursion()
File “program.pys3”, line 2, in infinite_recursion
infinite_recursion()
File “program.pys3”, line 2, in infinite_recursion
infinite_recursion()
File “program.pys3”, line 2, in infinite_recursion
infinite_recursion()
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Advantages of Recursion
The advantages of recursion are as follows:
- Using recursive functions helps to make code look clean, simple and elegant.
- Sequence creation becomes simpler and easier with recursion than using nested iterations.
- We can split down a complicated complex task into simpler and smaller sub-tasks using recursion.
Disadvantages of Recursion
The disadvantages of recursion are as follows:
- A recursive call that is a function calling itself multiple times takes a lot of time and memory which makes it inefficient and expensive.
- Sometimes the reasoning and the logic behind the recursion is tough to click.
- In case your code fails due to some small typo or logical error, it is very challenging to debug the recursive codes.
Frequently Asked Questions
Q.1. What is recursion in Python explain with example?
Answer: Recursion is the process in which the function calls itself, the call may be direct or indirect. Using recursion, certain problems like Towers of Hanoi, DFS of graphs etc can be solved easily.
The most well known physical world example of recursion is infinite images formed by two parallel mirrors. The image formed acts as an object and form a new image this way the process is defined in terms of itself and hence shows recursion.
Q.2. How does recursion work in Python?
Answer: When we call a function in python, a new local namespace is created by the interpreter. In recursion multiple instances of the same recursive function are running concurrently therefore for the function to have finite calls there is a base condition for every recursive function and that is the terminating condition where our function stops calling itself. This way in recursion we first break our problems to simpler subproblems until it reaches the base condition and concludes our answer by solving step by step from simpler to the main problem.
Q.3. Is recursion bad in Python?
Answer: Recursion can be considered bad in python because a recursive solution is generally slower than the iterative solution and also python’s stack depth is not unlimited so there are huge chances of stack overflow.
Although there are some advantages of recursion too, it helps to make code look clean, simple and elegant and problems involving sequence creation becomes simpler and easier with recursion than using nested iterations.
Q.4. What is recursion with an example?
Answer: Recursion is the process in which the function calls itself, the call may be direct or indirect. Using recursion, certain problems like Towers of Hanoi, DFS of graphs etc can be solved easily.
Example: A factorial of a number n is defined by n! where n! = 1*2*3*…*n
Let’s write a recursive code to find factorial of a number n
Code
# Code to print the Factorial of a number n
# Recursive factorial function
def recursive_factorial(n):
if n <= 1:
return 1
else:
return( n*recursive_factorial(n-1) )
n = 5
# check if the number of terms is valid
if n_terms <= 0:
print(“Invalid input ! Input must be a positive value”)
else:
print(“Factorial of given number is :”)
print(recursive_factorial(n))
Output
Factorial of the given number is :
120
