Understanding Recursion In the Most Practical Way

Hey Everyone. I hope your coding journey is going super smooth and you must have completed basic data structures and programming concepts like Loops, Functions, Conditional Statements, etc. If not then no worries, you can continue with this article. I can promise you that after reading this article, you will have a solid understanding of what recursion is and how it can be used in solving modern-world programming challenges.

You might heard from your seniors that recursion can be very scary if not taught properly. Also, this is the first step to learning advanced Data Structures and Algorithms like Graphs, Trees, and Dynamic Programming. From The interview's point of view, you might also be grilled upon the basic understanding of recursion.

Recursion In Real Life

Before becoming too technical, we will start with a common real-world example. Let's assume, for now, there's nothing like Recursion exists on this planet. Assume you are a worker who has to demolish a 12-storey building. What would be the first thing that will come to your brain? How will you proceed with this task? You will break each floor one by one.

But assume if the total floors of the building are 2000 ( Just Hypothetical:-P), would you still demolish each floor on one by one basis? No not in the thousand years. How cool it would be if you just had to demolish just one floor and taught your super fast companion to do the same thing again and again until the total floors in the building become zero. This is the core principle of recursion.

Now, let's take the same example again but this time you have your friend whose name is Recursion with you who can copy the task that you taught him until a certain condition is met. Now, you just broke the one floor and asked your friend to copy the same thing until the number of floors becomes zero. Now, Your Friend Recursion will do the same thing for the leftover floors.

For example, There are 100 floors in a building that needs to be demolished. Initially, you demolished the first floor which made the total floors to be 99. Now, your friend will do the same thing with decreasing inputs like first it broke the second floor, and then check whether the ending condition is met or not. if not it will keep on demolishing the floors until the time the condition is met.

Hope, you got the basic crux of the recursion. Now let's dive into the technical aspect of the above example. The stopping condition that you put before making the recursive calls is called BASE CASE. The task your friend recursion is making for various inputs is called RECURSIVE CALLS.

Technical Aspect of Recursion

If you are very versed in any programming language, you must know the concepts of functions. Recursion is nothing but calling the function again and again until and unless a certain base condition is met. Look below the code that finds the factorial of the nth number which is given in the integer format to the function.

def findingFactorial(n): // a function that takes n integer and returns its factorials
    if n==0:  // Base Case that stops the recursive calls when n becomes 0
        return 1
    else:
        return n*findingFactorial(n-1)  // recursive calls

Let's understand the above code. The function is just returning the factorial of the given integer. For example, you give 5 in the function so the factorial can be 5 * 4!. Similarly, for 4, it can be 4 * 3! and so on.

The base case makes sure that the factorial returns 1 when n becomes 0. For example factorial of 1 can be 1*0, here without a base case, we will end up returning 0 but the base case makes sure that 0 returns 1 and we end up returning 1 as this is the correct factorial for n=1.

Benefits of Recursion

Recursion is a very powerful technique to solve various programming challenges. You can use recursion to reverse the array, check for palindromes, Solving Graph-based problems, traverse various types of Trees, and Dynamic Programming. We won't dive into Dynamic Programming as of now but remember that it is just an optimization technique to make the recursive calls quite efficient.

Demerits of Recursion

We have talked too much about recursion but even the moon has its dark side so does recursion. Even though recursive calls seem convenient, they are associated with using extra memory as they are associated with using auxiliary stack space for each call. As you call recursion for multiple inputs, you will compromise with the memory aspect of your program. Recursion without proper optimization techniques might slow down your program or may take up huge space.

Bottom Line

I hope you got a good idea of what recursion is after reading this article. To understand the concept in a much better way, think about certain real-world cases then come up with your base cases. Thinking about the base case is the only challenging part of recursion. After a little hustle, you will become quite strong in this concept.