Let us start with the definition of recursion in the data structure. We will later discuss different types of recursion and how recursion is used to solve different problems.
Table of Contents
What is recursion?
In simple words, recursion is a problem solving, and in some cases, a programming technique that has a very special and exclusive property. In recursion, a function or method has the ability to call itself to solve the problem. The process of recursion involves solving a problem by turning it into smaller varieties of itself.
The process in which a function calls itself could happen directly as well as indirectly. This difference in call gives rise to different types of recursion, which we will talk about a little later. Some of the problems that can be solved using recursion include DFS of Graph, Towers of Hanoi, Different Types of Tree Traversals, and others. To learn about recursion and other data science concepts, check out IIIT-B’s data science online courses.
How does recursion work?
The concept of recursion is established on the idea that a problem can be solved much easily and in lesser time if it is represented in one or smaller versions. Adding base conditions to stop recursion is another important part of using this algorithm to solve a problem.
People often believe that it is not possible to define an entity in terms of itself. Recursion proves that theory wrong. And if this technique is carried out in the right way, it could yield very powerful results. Let us see how recursion works with a few examples. What is a sentence? It can be defined as two or more sentences joined together with the help of conjunction. Similarly, a folder could be a storage device that is used to store files and folders. An ancestor could be a parent of one and an ancestor of another family member in the family tree.
Recursion helps in defining complex situations using a few very simple words. How would you usually define an ancestor? A parent, a grandparent, or a great grandparent. This could go on. Similarly, defining a folder could be a tough task. It could be anything that holds some files and folders that could be files and folders in their own right, and this could again go on. This is why recursion makes defining situations a lot easier than usual.
Recursion is also a good enough programming technique. A recursive subroutine is defined as one that directly or indirectly calls itself. Calling a subroutine directly signifies that the definition of the subroutine already has the call statement of calling the subroutine that has been defined.
On the other hand, the indirect calling of a subroutine happens when a subroutine calls another subroutine, which then calls the original subroutine. Recursion can use a few lines of code to describe a very complex task. Let us now turn our attention to the different types of recursion that we have already touched upon.
Also read: Top 6 Programming Languages to Learn
Types of recursion
There are only two types of recursion as has already been mentioned. Let us see how they are different from one another. Direct recursion is the simpler way as it only involves a single step of calling the original function or method or subroutine. On the other hand, indirect recursion involves several steps.
The first call is made by the original method to a second method, which in turn calls the original method. This chain of calls can feature a number of methods or functions. In simple words, we can say that there is always a variation in the depth of indirect recursion, and this variation in depth depends on the number of methods involved in the process.
Direct recursion can be used to call just a single function by itself. On the other hand, indirect recursion can be used to call more than one method or function with the help of other functions, and that too, a number of times. Indirect recursion doesn’t make overhead while its direct counterpart does.
When is recursion used?
There are situations in which you can use recursion or iteration. However, you should always choose a solution that appears to be the more natural fit for a problem. A recursion is always a suitable option when it comes to data abstraction. People often use recursive definitions to define data and related operations.
And it won’t be wrong to say that recursion is mostly the natural solution for problems associate with the implementation of different operations on data. However, there are certain things related to recursion that may not make it the best solution for every problem. In these situations, an alternative like the iterative method is the best fit.
The implementation of recursion uses a lot of stack space, which can often result in redundancy. Every time we use recursion, we call a method that results in the creation of a new instance of that method. This new instance carries different parameters and variables, which are stored on the stack, and are taken on the return. So while recursion is the more simple solution than others, it isn’t usually the most practical.
Also, we don’t have a set of pre-defined rules that can help choose iteration or recursion for different problems. The biggest benefit of using recursion is that it is a concise method. This makes reading and maintaining it easier tasks than usual. But recursive methods aren’t the most efficient methods available to us as they take a lot of storage space and consume a lot of time during implementation.
Keeping in mind a few things can help you decide whether choosing a recursion for a problem is the right way to go or not. You should choose recursion if the problem that you are going to solve is mentioned in recursive terms and the recursive solution seems less complex.
You should know that recursion, in most cases, simplifies the implementation of the algorithms that you want to use. Now if the complexities associated with using iteration and recursion are the same for a given problem, you should go with iteration as the chances of it being more efficient are higher.
Also check out: 23 Best Computer Programming Courses To Get a Job
However, there could be situations in which making a decision may not be that easy. You have to choose between efficiency and simplicity. If you are an experienced designer, you would know exactly when to give more importance to efficiency and when choosing simplicity or conciseness over it is the way to go.
If you are curious to learn about data structure, data science, check out IIIT-B & upGrad’s Executive PG Programme 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.
What is the most common real-life application of recursion?
Recursion is a process in which the function calls itself indirectly or directly in order to solve the problem. The function that performs the process of recursion is called a recursive function. There are certain problems that can be solved pretty easily with the help of a recursive algorithm.
The most common real-life application of recursion is when you are calculating how much money you have in a box filled with Rs. 100 notes. If there are too many notes, then you might just ask your friend to do the same work by dividing the entire stack into two. Once you both are done with counting, you will just add up both the results in order to get the total amount.
What are the properties that a recursive function must have?
A recursive function has the capability to continue as an infinite loop. There are two properties that have to be defined for any recursive function to prevent it from going into an infinite loop. They are:
1. Base criteria – There has to be one predefined base condition. Whenever this base criterion is fulfilled, the function will stop calling itself.
2. Progressive approach – The recursive calls should consist of a progressive approach. Whenever a recursive call is made to the function, it should be reaching near the base condition.
What are the advantages and disadvantages of recursion?
Some of the advantages of recursion are that you only need to define the base condition and the recursive case in a recursive function. This makes the code pretty simple and short as compared to an iterative code, and some problems like Tree Traversal and Graph are inherently recursive.
The biggest disadvantages of recursion are that there are greater space requirements for recursive functions as compared to an iterative program because every function call has to remain in the stack until the base condition is met, and there are greater time requirements, too, because the stack grows after each function call, and the final answer can only be returned after popping all the elements from the stack.