The problem of Grid Traveler is one of the best problems you can use to learn recursion. It helps you better understand the basics of recursion. If you want to learn more about recursion, you can check out my other article here.
So the problem goes like this, you are a two-dimensional grid traveler. You are basically in a two-dimensional array. From the beginning, your location is the upper-left square, and your goal is to find the number of paths leading you to the lower-right corner of the grid. In other words, how many ways can you reach the lower-right corner? You must only move one step at a time, either to the right cell or the bottom cell of the current point.
Now that we understand the problem let us dive into the solution. But first, let us break down the problem and study all the parts individually.
Understand the task and simplify the problem
Think about the conditions and the basic features this problem has. You are now a grid traveler, so you better start to think like one. The grid we talk about is a two-dimensional array or an array within an array if you will. So for sure, the case either involves a loop, or a recursion, as many problems do in programming.
Now comes the “Understand the task” part. You are in an array, and there are two steps you can take, either right or down. There is a beautiful detail to understand here. Let’s say you choose to move right. When you do, you indirectly decrease the size of your grid. The reason is that you cannot reach your left side of the grid from the newest position. The problem requires you only to move one square right or one square down. Then let’s assume you go one down. Now, you have no access to the grid row you left behind, the one above you. So, as a result, the problem is now smaller than the size it was from the beginning.
As you can see here, you eliminate the leftmost column of the grid by moving one cell to the right.
And here you move one down, so you now downsized your grid by one entire row.
Grid traveler going back and forth
There is another beautiful thing to understand. Whenever we encounter a recursion, there is a beautiful feature to it. Simply put, while solving problems like this one, we are in the action of moving. And during the motion, in every step, we have a choice to make. In this case, we have to choose to move either right or down. However, the key strategy for solving similar problems is that we eventually need to take every possible path at any given point. If we do not take all the roads, there is no way to find all the ways we can travel from point A to B in our grid.
So what I am trying to achieve by the previous point is, with recursion, you can dynamically choose any road, follow that road, come back to the exact point, and carry on with all the other paths that are still left. Isn’t it beautiful?
That is possible because, for all the function calls, we will eventually hit base cases and return to the places where they were called. In our case, this line is on row 8 of the code snippet shown below. The code is written using JavaScript. However, code logic itself will mostly stay the same in other languages. Whenever the first call to the function “traveler” is finished, we will continue to the next function call. There it is. This way, we can look at all the possible paths/choices we want without leaving anything unchecked. This is the beauty of this problem and the recursion overall. So the point is, with recursion, you can dynamically choose any road, follow that road, return to the exact point, and carry on with all the other paths that are still left. Isn’t it beautiful? The grid traveler goes back and forth till the answer is obvious.
Let’s have a look at the code. It will be much easier to understand the concept after we study the code.
const traveler = (x, y, memo = {}) => {
if (memo[`${x}-${y}`]) return memo[`${x}-${y}`];
// base cases
if (x === 1 && y === 1) return 1;
if (x === 0 || y === 0) return 0;
const ways = traveler(x - 1, y, memo) + traveler(x, y - 1, memo);
memo[`${x}-${y}`] = ways;
return ways;
}The first line of the code I will explain later. The critical point to understand is our so-called “choices” in the recursive calls. You can see that we add two results of two separate function calls to each other. This approach is called Binary recursion. You can connect the dots, right? The function calls are the two choices that we discussed earlier. The first one that decreases the value of x by 1 is equivalent to moving one cell to the right. And the call that decreases the value of y is moving one cell down. Though we already discussed this, reinforcing the point is a good idea. It is always a good idea to see the concept in action. Remember, practice is everything.
The code coming after that is nothing but our base cases. We defined them, so our program knows when to stop and return the desired value. If we do not specify those conditions correctly, our code will simply break, and our call stack will be full. Basically, we have two base cases. The first one indicates that there is only one cell left to consider. Because we move only right and down one cell at a time, and if it is the case when we are left with only one cell, we can be sure that we got to the lower-right corner. You can already guess that this is a win situation. This means that we found one solution to our problem.
The rest is up to the recursion. As we discussed, we will choose to either move right or down, the code will call the same function from there, and at some point in the future, we will again be back to the choice that we made, then our code will take the other choice, and again the code will be executed till we hit one of our base cases. This way, we solved the problem of considering every possible way on our way without leaving any reachable cell unchecked.
Let us continue to learn, grow, and be passionate about our beloved programming. Remember that with every bit of success, we come closer to making this world a better place, so be inspired and keep inspiring others. See you in the next chapter of our journey.