HomeBlogData SciencePython Recursive Function Concept: Python Tutorial for Beginners

Python Recursive Function Concept: Python Tutorial for Beginners

Read it in 7 Mins

Last updated:
18th Mar, 2020
Views
1,500
In this article
View All
Python Recursive Function Concept: Python Tutorial for Beginners

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.

Profile

Rohit Sharma

Blog Author
Rohit Sharma is the Program Director for the UpGrad-IIIT Bangalore, PG Diploma Data Analytics Program.

1Why is recursion so important?
If you are a programmer, then it is very important for you to think recursively. The reason is that recursive functions will help you to break down a complex program into a smaller one. You will also notice that recursive solutions are much simpler to read as compared to iterative ones.

You will often see that certain programs take up a huge amount of space and lines of code for functioning. There are several scenarios where these programs can be simplified by adding a recursive function so that the function is called again and again whenever it is required. So, you won't have to write so many extra lines of code, and the work also gets done effectively.
2What are the applications of recursion?
There are plenty of practical applications of recursion seen in both computing functions and real life. Without the use of recursion, it is not possible to express certain math functions such as Fibonacci sequence, Ackermann function, for determining whether a number is a palindrome or not, draw a type of fractal, and much more.

There are several software and apps which are built through these math functions. For instance, Candy Crush uses these math functions and recursion for the generation of a combination of tiles. Other than that, chess is also a classic example of the application of recursion. A majority of searching algorithms that we utilize today also make use of recursion.
3What are the fundamental rules of recursion?
Recursive functions are the ones that can call themselves for solving a complex problem by simplifying it in different small steps. There are four fundamental rules of recursion. There has to be a base case that can be solved without the help of recursion. Every case that should be solved recursively should always make progress towards the base case. Use proof by induction in the designing rule for assuming that all the recursive calls work. You should never use separate recursive calls for solving the same instance of the problem. Instead, you should go with dynamic programming.

Suggested Blogs

OLTP Vs OLAP: Decoding Top Differences Every Data Professional Must Know
1500
Several businesses use online data processing systems to boost the accuracy and efficiency of their processes. The data must be used before processing
Read More

by Rohit Sharma

12 Apr 2023

Understanding the Concept of Hierarchical Clustering in Data Analysis: Functions, Types & Steps
1500
Clustering refers to the grouping of similar data in groups or clusters in data analysis. These clusters help data analysts organise similar data poin
Read More

by Rohit Sharma

08 Apr 2023

Harnessing Data: An Introduction to Data Collection [Types, Methods, Steps & Challenges]
1500
Data opens up the doors to a world of knowledge and information. As the currency of the information revolution, it has played a transformational role
Read More

by Rohit Sharma

08 Apr 2023

A Brief Guide to Working With ‘ALTER’ Command in SQL-Know the Ins and Outs!
1500
Structured Query Language (SQL) is necessary for most, if not all, industries worldwide. Starting from IT sector to finance and even healthcare, SQL m
Read More

by Rohit Sharma

06 Apr 2023

Data Lake Vs Data Warehousing: Key Differences You Should Know
1500
Data has become a very crucial part of every company. Data has several associated ingredients to acquire its most value, such as gathering extensive v
Read More

by Rohit Sharma

06 Apr 2023

Data Science vs Business Intelligence: Difference Between Data Science and Business Intelligence
1500
If there’s one thing that’s common to almost all sectors of modern industry, it is Big Data. While data is the new currency of the 21st century, exper
Read More

by Rohit Sharma

26 Mar 2023

Data Science Career Path: 12 Demanding & Diverse Roles
1500
A Brief Overview “Data Science” is the new buzzword among millennials as this multidisciplinary field of computer science offers a wide range of care
Read More

by Rohit Sharma

26 Mar 2023

What is Data warehousing? Type, Definition & Examples
1500
What is Data Warehousing? Data warehousing refers to a process where data is collected from different sources and managed well to provide insights th
Read More

by Pavan Vadapalli

20 Feb 2023

Top 10 Software Engineering Books to Read to Improve Your Skills [US]
1500
Software engineering and development is an ever-growing subject. Even if you have completed your academic studies, there is still plenty of scope to l
Read More

by Pavan Vadapalli

19 Feb 2023