Python Recursive Function Concept: Python Tutorial for Beginners

# Python Recursive Function Concept: Python Tutorial for Beginners

Last updated:
18th Mar, 2020
Views
1,500
View All  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.

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.

## 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

 Executive Post Graduate Programme in Data Science from IIITB Professional Certificate Program in Data Science for Business Decision Making Master of Science in Data Science from University of Arizona Advanced Certificate Programme in Data Science from IIITB Professional Certificate Program in Data Science and Business Analytics from University of Maryland 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

 SL. No Top Data Science Skills to Learn 1 Data Analysis Online Certification Inferential Statistics Online Certification 2 Hypothesis Testing Online Certification Logistic Regression Online Certification 3 Linear Regression Certification Linear Algebra for Analysis Online Certification

## 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.

upGrad’s Exclusive Data Science Webinar for you –

## 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

 Data Science Career Path: A Comprehensive Career Guide Data Science Career Growth: The Future of Work is here Why is Data Science Important? 8 Ways Data Science Brings Value to the Business Relevance of Data Science for Managers The Ultimate Data Science Cheat Sheet Every Data Scientists Should Have Top 6 Reasons Why You Should Become a Data Scientist A Day in the Life of Data Scientist: What do they do? Myth Busted: Data Science doesn’t need Coding Business Intelligence vs Data Science: What are the differences?

## 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.  #### Rohit Sharma

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

Select Course
Select
By tapping submit, you agree to  UpGrad's Terms & Conditions

#### Data Science Skills to Master

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.