In the world of computer science, recursion refers to the technique of defining a thing in its own terms. In other words, a recursive function calls itself for processing. In this article, we will understand the concept of recursive function in Python, a widely-used programming language of the 21st century.
What is Python Recursion?
In Python, a group of related statements that perform a specific task is termed as a ‘function.’ So, functions break your program into smaller chunks. And it is common knowledge that a function can call other functions in Python.
But some other functions can call themselves. These are known as recursive functions. Consider two parallel mirrors placed facing one another. Now, any object that is kept between the mirrors would be reflected recursively.
Let us go into detail about the recursive function to understand its working clearly.
Learn data science to gain edge over your competitors
The Recursive Function
We know that a recursive function in Python calls itself as it is defined via self-referential expressions, i.e., in terms of itself. It keeps repeating its behaviour until a particular condition is met to return a value or result. Let us now look at an example to learn how it works.
Also read: Python Interview Questions & Answers
Suppose that you want to find out the factorial of an integer. Factorial is nothing but the product of all numbers, starting from 1 to that integer. For instance, the factorial of 5 (written as 5!) would be 1*2*3*4*5*6, i.e., 720. We have a recursive function calc_factorial(x), which is defined as follows:
def calc_factorial(x):
#Recursive function to find an integer’s factorial
if x == 1:
return 1
else
return (x * calc_factorial(x-1))
What would happen if you call this function with a positive integer like 4? Well, each function call will add a stack frame until we reach the base case (when the number reduces to 1). The base condition is required so that the recursion ends and does not go on indefinitely. So, in the given case, the value 24 will be returned after the fourth call.
Our learners also read: Top Python Free Courses
Implementation of Recursive Function in Python
There can be varied applications of recursive functions in Python. For instance, you want to make a graphic with a repeated pattern, say a Koch snowflake. Recursion can be used for generating fractal patterns, which are made up of smaller versions of the same design.
Another example is that of game-solving. You can write recursive algorithms for solving Sudoku and numerous complex games. Recursion is most commonly used in searching, sorting, and traversal problems.
A striking feature of the function is that recursive implementation allows backtracking. So, recursion is all about building a solution incrementally and removing those solutions that do not satisfy the problem constraints at any stage. Two things are necessary to achieve this – maintaining state and suitable data structure. Read on to get familiar with these terms.
Read: Python Developer Salary in India
Maintaining the state
Each recursive call in Python has its own execution context. While dealing with recursive functions in Python, you have to thread the state through each recursive call. With this, the current state becomes a part of the current call’s execution context. You can also keep the state in global scope.
For example, if you are using recursion to calculate 1+2+3+4+…….+10. Here, the current number you are adding and the sum accumulated to that point forms the state that you need to maintain. Maintaining the state involves passing the updated current state as arguments through each call. Here’s how you can do it.
Explore our Popular Data Science Online Certifications
def sum_numbers(current_number, accumulated_sum)
#Base case
#Return final state
if current number==11:
return accumulated_sum
#Recursive case
#Thread the state through recursive call
Else:
return sum_numbers(current_number + 1, accumulated_sum + current_number)
Alternatively, you can use the global mutable state. To maintain state using this method, you keep the state in global scope.
current_number = 1
accumulated_sum = 0
def sum_numbers():
global current_number
global accumulated_sum
#Base case
if current_number==11
return accumulated_sum
#Recursive case
else:
accumulated_sum = accumulated_sum + current_number
current_number = current_number + 1
return sum_numbers()
Top Data Science Skills You Should Learn
Recursive Data Structures
A data structure is considered recursive if it can be defined in terms of smaller and simpler versions of itself. Examples of recursive data structures include lists, trees, hierarchical structures, dictionaries, etc. A list can have other lists as elements. A tree has sub-trees, leaf nodes, and so on.
It is important to note here that the structure of recursive functions is often modeled after the data structures that it takes as inputs. So, recursive data structures and recursive functions go hand in hand.
Recursion in Fibonacci Computation
Italian mathematician Fibonacci first defined the Fibonacci numbers in the 13th century to model the population growth of rabbits. He deduced that starting from one pair of rabbits in the first year, the number of rabbit pairs born in a given year equals the number of rabbit pairs born in each of the last two years. This can be written as: Fn = Fn-1 + Fn-2 (Base cases: F0=1 and F1=1).
When you write a recursive function to compute the Fibonacci number, it can result in naive recursion. This happens when the definition of the recursive function is naively followed, and you end up recomputing values unnecessarily. To avoid recomputation, you can apply lru_cache decorator to the function. It caches the results and saves the process from becoming inefficient.
Read more: Top 10 Python Tools Every Python Developer Should Know
upGrad’s Exclusive Data Science Webinar for you –
How upGrad helps for your Data Science Career?
Pros and Cons of Recursive
Recursion helps simplify a complex task by splitting it into sub-problems. Recursive functions make cleaner code and also uncomplicate sequence generation. But recursion does not come without its limitations. Sometimes, the calls may prove expensive and inefficient as they use up a lot of time and memory. Recursive functions can also be difficult to debug.
Read our popular Data Science Articles
Wrapping Up
In this article, we covered the concept of Python recursion, demonstrated it using some examples, and also discussed some of its advantages and disadvantages. With all this information, you can easily explain recursive functions in your next Python interview!
If you are curious to learn about data science, check out IIIT-B & upGrad’s PG Diploma in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.
