Recursion in Python
In this Python article, we will discuss how to create a recursive function and how does recursion works in python with some examples.
1. How does Recursion work in python?
Recursion can be defined as an operation performed multiple times with different inputs. A recursive function can be understood as a function that calls itself.
Python supports the recursion of function, as we know that a function can call another function. In the same way, a function can call itself as many numbers of time with different inputs forming a recursion function.
Recursion is generally regarded as a mathematical and programming concept. The recursive function must have a base condition as it is quite easy to write a never-terminating function if there is no condition to stop. So it is very important to have a condition that can stop the recursion.
Recursion is very effective and this mathematical approach of programming tries to run the function again and again with different inputs.
Recursion works with the help of a stack, it puts the function called in a stack until the last recursive function, once the work is done, the functions are removed from the stack one by one.
Syntax
def recursive_function(parameter): #function is defined
statements
if (base condition):
return some_value
recursive_function(modified parameters) #recursive call
...
recursive_function(parameter) #First call of the function Recursive functions are easy to implement and the best way to find correctness is by testing and modifying them. Let’s take some examples to understand recursion better.
1.1. Binary search using recursion
We can implement a binary search program with the help of a recursion function.
# Binary search in Python by recursion
def binarysearch(arr, start, end, x):
if end >= start: # base condition
mid = (start + end) // 2
if arr[mid] == x: # If value found at the mid
return mid
elif arr[mid] > x: # If value is smaller than mid
return binarysearch(arr, start, mid-1, x)
else:
return binarysearch(arr, mid+1, end, x)
else:
return 0 # Value not found
arr = [1, 3, 5, 9, 12, 17, 19]
x = 17
# Function call
result = binarysearch(arr, 0, len(arr)-1, x)
if result != 0:
print("Value found at index", str(result))
else:
print("Value not found in array")
Output Value found at index 5
1.2. Find Factorial using recursion
Factorial of a number n is a product of all numbers(integers) from 1 to n. It means that factorial of 5 (denoted by 5!) is 5*4*3*2*1=120
Syntax 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 x 2 x 1! #1!=1
# Factorial of any number
def factorial(x):
if x == 1:
return 1 # base condition to stop the iteration
else:
return (x * factorial(x-1)) # recursive call
x = int(input("Enter the number "))
print("Factorial is ", factorial(x)Output Enter the number 5 Factorial is 120
The factorial of the number is calculated by multiplying it until the number is equal to one. This recursive call can be explained in the following steps.
factorial(5) # 1st function call 5 5 * factorial(4) # 2nd function call 4 5 * 4 * factorial(3) # 3rd function call 3 5 * 4 * 3 * factorial(2) # 4th function call 2 5 * 4 * 3 * 2 * factorial(1) # 5th function call 1 5 * 4 * 3 * 2 * 1 # return 5th call as x=1 5 * 4 * 3 * 2 # return from 4th call 5 * 4 * 6 # return from 3rd call 5 * 24 # return from 2nd call 120 # return from 1st call
1.3. Print Fibonacci series using recursion
Let’s implement the program to print Fibonacci series using recursion.
# Fibonacci Series
def fibonacci_series(x):
if x <= 1: # base condition
return x
else:
return(fibonacci_series(x-1) + fibonacci_series(x-2))
total_terms = 7
if total_terms <= 0: # Fibonacci series term cannot be less than 1
print("Input Invalid ! Give some positive input")
else:
print("The series formed is:")
for i in range(total_terms):
print(fibonacci_series(i))Output The series formed is: 0 1 1 2 3 5 8
The Python interpreter has a limit to the depths to call the recursion function to avoid infinite recursions which results in a stack overflow error.
By default, there is a maximum depth of recursion which is set to 1000. If the program or the recursive function crosses the limit then the results in RecursionError. Let’s look at one such condition with the help of a small example.
Note: We can also update this limit if we want and this is the default limit.
def recur(): recur() #no base condition recur()
Output Traceback (most recent call last): File "", line 1, in File "", line 2, in recur File "", line 2, in recur File "", line 2, in recur [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded
2. Advantages of recursion
- Recursion splits a complex problem function into simpler and smaller sub-problems.
- The code looks simpler and easier to understand.
- It is better to use recursion for sequence creation rather than iteration.
3. Disadvantages of recursion
- It takes too much space and time which can be expensive for the user.
- Debugging the recursive functions is not easy.
- It is sometimes hard to follow through with the logic behind the recursion.
4. What is Tail Recursion
Tail-recursion can be defined as a special kind of recursion in which the last statement of a function is a recursive call. This recursion may be automated which means instead of generating a new stack frame, the output will be returned in the current stack which is performing the request.
The compiler makes tail-recursion optimized which becomes better than non-tail recursive functions.
Can the use of a tail-recursive function make it possible to optimize a program over a non-tail-recursive function?
Let’s take an example to understand this concept easily. The example below has the function to calculate the factorial of a number n. If we focus, we can clearly factorial(x) use the output of factorial(x-1).
So we can say that the call to factorial(x-1) is not the last thing done by factorial(x) which means that the function looks like a tail-recursive but it is a non-tail-recursive function.
# non-tail recursive factorial function
def factorial(x):
if (x == 0): # base condition
return 1
return x * factorial(x-1)
print(factorial(5))Output 120
We can make the function factorial into a tail-recursive function. To do so we have to pass one more argument which will accommodate the factorial value. When x will reach 0, it returns the final value of the factorial of the desired number.
# A tail recursive factorial function
def factorial(x, y=1):
if (x == 0): # base condition
return y
return factorial(x - 1, x * y)
print(factorial(5))Output 120
5. Conclusion
In this article we learned about
- What is recursion with some examples and its advantages and disadvantages
- What is Tail recursion with an example
Helpful Links
Please follow the Python tutorial series or the menu in the sidebar for the complete tutorial series.
Also for examples in Python and practice please refer to Python Examples.
Complete code samples are present on Github project.
Recommended Books
An investment in knowledge always pays the best interest. I hope you like the tutorial. Do come back for more because learning paves way for a better understanding
Do not forget to share and Subscribe.
Happy coding!! ?