Python is a high-level, interpreted programming language, and is one of the most popular programming languages present in the software industry. One of the most important concepts in python is that of recursion. Let us have a look at it in detail.
In python, recursion is a term used to describe the situation in which a function directly or indirectly calls itself inside its body.
The idea behind recursion arises from mathematics. This allows a programmer to break down complex problems into simpler problems that are manageable and easy to understand.
Programmers usually use recursion to make the code look more elegant instead of using nested iterations which often results in the code looking too shabby and complex.
Recursion does have a few disadvantages though. The logic of recursion is usually relatively difficult to understand.
If the programmer is not careful, the program could enter an infinite loop which is a very dangerous situation where the code never ceases execution.
The syntax to perform recursion in python using functions is pretty straightforward and is as follows. We call the same function inside its definition. Do keep in mind the indentations required to specify the function body.
def func():
<statements>
func()
<statements>Let us look at a simple example wherein we use the concept of recursion to calculate the factorial of a given positive integer.
A factorial of a positive integer is the product of all positive integers less than or equal to that number.
For example, the factorial of 3 is the product of 1,2, and 3 which is equal to 6.
In this example, we look at the usage of the concept of recursion to calculate the factorial of a given positive integer. We first define a function named fact which takes in a parameter n. Next, we specify a base condition that helps in the termination of recursion. This shall be the case when n is 0.
We return the answer as 1 because mathematically, the factorial of 0 is defined to be 1. Next, we have the main step for recursion which is executed when the value of n is greater than 0.
This step takes advantage of the fact that the factorial of a number is equal to the product of the number and the factorial of the number that is one less than it i.e. fact(n) = n * fact(n-1). We finally returned the answer.
In the example below, we have a variable a with a value 3. The function fact is first called with this value of 3 as a parameter and the result is stored in another variable b which is later printed.
The expected output is 6. Let us see how the program gets executed step by step after the function is first called with parameter 3. Since 3 is not equal to 0, it does not fall in the base case and we move to the next statement. Here we define the local variable answer to hold the value of 3 multiplied by the factorial of 2, which is 3-1.
The function fact is then called once again with the parameter as 2. This function call has its own local variable answer that has the value of the product of 2 with the factorial of 1, which results in another function call. The function call with parameter as 1 also results in another similar function call with parameter as 0.
This function call falls into the base case and a value of 1 is returned. Next, the answer for the previous function call is calculated as 1*1 and the answer of 1 is returned. Next, the answer of the previous function call is calculated as 2*1 and the answer of 2 is returned. Next, the answer of the original function call is calculated as 3*2 and the answer of 6 is returned finally which is stored in the variable b and printed.
Let us take a look at the python code and corresponding output for this method -
def fact(n):
# Base case when n = 0
if (n==0):
return 1
# Main step for recursion
answer = n * fact(n-1)
# Returning the answer
return answer
a = 3
# Calling the function with parameter 3
b = fact(a)
# Printing the result
print(b)Output
6
We cannot have an unlimited number of recursive calls of a function.
If we forget to add a condition that helps in terminating recursion, an exception would be raised.
In the example below, we define a function named func and inside the body, we simply call the function recursively.
This would result in an infinite execution of code which the python interpreter cannot allow.
Therefore, a RecursionError is raised. By default, the maximum depth of recursion in python is set to 1000.
Let us look at the python code and corresponding output for this example -
def func():
# Calling the function recursively
func()
# Calling the function
func()Output
RecursionError: maximum recursion depth exceeded
In this topic, we have learned the use and advantages of recursion in a Python program, following some simple running examples of programs, thus giving us an intuition of how this concept could be applied in real-world situations. Feel free to reach out to info.javaexercise@gmail.com in case of any suggestions.