Fall in ?? with Recursion

Hello everyone, in your journey of programming you would have used recursion at least once. Today, I want to introduce you to recursion in a much better way.

What is Recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.

source: https://www.geeksforgeeks.org/recursion/

You would be wondering that, "Ah! I know that a function calling a function directly or indirectly is called recursion. What's new in that?" Everyone of us have learned this right?

Yup, you are right but there's more to that. Let's get on to that.

If you are from a Mathematics background, you would have already heard of the Principle of Mathematical Induction aka PMI.

I'm assuming that you have an idea of PMI. If not, here's a link to know more about it.

Recursion is nothing but PMI. What??? ??

You: "So you are saying that I've already learned recursion in high school?"

Yes, you've already learned recursion in high school.

The basic concept of PMI is to prove things and it consists of only two steps:

1. when a statement is true for a natural number n = k,?then it will also be true for its successor, n = k + 1;
2. the statement is true for?n?= 1;?then the statement will be true for every natural number?n.

You: "We all know that! How is it related to recursion??? ??"

I would like to tell you a story.

When I started using recursion, I used to think about how my function's gonna behave for certain specific values and I used to make changes to the function accordingly.

Believe me, It's the most hilarious way of approaching a problem using recursion.

You: "Enough talking, just get to the point..."

Here are the simple steps:

1. Assume that your function is gonna work in every condition.
2. Pick out the smallest/largest possible input for which it breaks. That's your Base Case ??.
3. Now solve your problem for a particular case/s.

That's it. You're done solving the problem.

You don't believe me right? ??

I'm going to solve a Leetcode's problem using the same concept. I got it here.

Here's a link to the problem: https://leetcode.com/problems/max-area-of-island/

As we can see the matrix, we need to find the island with the maximum area and return it's area.

Suppose, I have a superpower through which I can clone myself ??????

Don't worry, you've got this superpower too ??????

Let's solve this problem now.

First, we'll look for land i.e. represented by 1 iterating matrix the usual way...

for (int i = 0; i < grid.size(); i++) {
    for (int j = 0; j < grid[i].size(); j++) {
        if (grid[i][j] == 1) {
            // Got the land...
            // Do something here...
        }
    }
}        

Now, I'll use my superpower and make 4 clones of me to go to all the 4 directions possible .i.e Up, Down, Left and Right.

I will now count the area where I am standing currently i.e. 1 and ask all my 4 clones to go to their specified direction to get the area.

Don't forget to flag ?? the area that we have already visited.

The new function would look something like this:

int getArea(vector<vector<int>>& grid, int i, int j) {
? ? ? ? int myArea = 1; // Counting my own area
? ? ? ? grid[i][j] = 2; // Marking the visited area
? ? ? ? int left = getArea(grid, i, j-1);    // Left clone
? ? ? ? int top = getArea(grid, i-1, j);     // Top clone
? ? ? ? int right = getArea(grid, i, j+1);   // Right clone
? ? ? ? int bottom = getArea(grid, i+1, j);  // Bottom clone
}        

I would now return the sum of my own area and the area all my clones got for me...

int getArea(vector<vector<int>>& grid, int i, int j) {
? ? int myArea = 1; // Counting my own area
? ? grid[i][j] = 2; // Marking the visited area
? ? int left = getArea(grid, i, j-1);    // Left clone
? ? int top = getArea(grid, i-1, j);     // Top clone
? ? int right = getArea(grid, i, j+1);   // Right clone
? ? int bottom = getArea(grid, i+1, j);  // Bottom clone
    return myArea + left + top + right + bottom;
}        

Very Imp: There has to be some sort of validation (base case) for the recursion to stop.

In our case, it would be two cases:

• Either we don't find land i.e. 0 or go to already visited land i.e. 2
• We need to avoid going out of bounds (out of the grid)

After writing the base cases, our function should look something like this:

int getArea(vector<vector<int>>& grid, int i, int j) {

    // Avoiding going out of bounds
    if (i < 0 || i >= grid.size()) return 0;
    // Avoiding going out of bounds
? ? if (j < 0 || j >= grid[i].size()) return 0;
    
    // Checking if there's land or else return 0
? ? if (grid[i][j] != 1) return 0;
 
    // Counting my own area
? ? int myArea = 1; 
 
    // Marking the visited area
? ? grid[i][j] = 2;
 
    // Asking the clones to get the area...
? ? int left = getArea(grid, i, j-1);    // Left clone
? ? int top = getArea(grid, i-1, j);     // Top clone
? ? int right = getArea(grid, i, j+1);   // Right clone
? ? int bottom = getArea(grid, i+1, j);  // Bottom clone
 
    // Returning sum of all the areas and our own area
    return myArea + left + top + right + bottom;

}        

Since, I've got this superpower to clone myself, my clones posses the same superpower. This is the key to understand recursion...

Now, Imaging you find land and send all your clones to get the area. The clones will again do the same thing and will get the area of the whole island.

Let's modify our main function so that we can store the max area of the island

int maxArea = 0;

for (int i = 0; i < grid.size(); i++) {
    for (int j = 0; j < grid[i].size(); j++) {
        if (grid[i][j] == 1) {
            // Got the land...
            maxArea = max(getArea(grid, i,j), maxArea);
        }
    }
}

return maxArea;
        

What this function will do is it will try to find the area of the whole island once it gets land and store the max area.

It will continue doing so until it reaches the end of the grid.

?? Fun Fact: You can only have this cloning superpower if you start using recursion.

I hope that you got a gist of "What recursion is" and "How it works"

Once you are comfortable with recursion, I hope you'll find Memoization and Dynamic Programming a little bit easier to solve/approach.

This is just a start in the world of recursion guys. I hope you'll solve more problems around the same.

Happy Coding...??????