2.1.5. Challenges with Recursion

So, as you might guess, since we are looking at these kind of inductive formulations and recursive programs, what we are really looking for is the inductive formulation of the grid path. ... So, if I count the task coming to the two neighbours, then each of those paths can be extended to reach the current node.

In this chunk, we begin by establishing the basis for solving the problem of finding paths in a grid using recursion. We determine that there are only two possible ways to reach a point on the grid : coming from the left or from below. Consequently, we can deduce a formula that tells us how many paths can be formed to reach any point (i,j) based on the paths to (i-1,j) and (i,j-1). This step serves as the foundation of our inductive approach: any path reaching (i,j) adds the paths leading to its neighbors—either from the left (i, j-1) or from below (i-1, j). Additionally, we have to consider boundary conditions for the first row and column, where paths can only come from one direction.

Imagine a delivery person trying to reach a new address in a city laid out as a grid. The person can only move up or right. To understand how many different routes exist to get from the starting point (the warehouse) to the new address, we realize that the person can either come from the street to the left or from the street below. This reasoning helps us compute the total routes available to this destination, similar to how we compute paths in the grid.

So, if you look at our grid, in general, then if we look at the leftmost column, let us start the bottom row. ... It is important that it is not 0 because remember, that if it is 0, then everywhere you are just adding things and nothing will come, you will get no paths.

This chunk emphasizes the importance of boundary conditions when calculating paths. The grid is evaluated from the bottom row and leftmost column, where paths can only come from one direction due to limited neighbors. For example, any cell in the leftmost column can only be accessed from the cell directly below it, as there are no cells to the left. Importantly, the number of ways to be at the starting point (0,0) is defined as one, since there exists only one way to remain there. These constraints are crucial as they guide our calculations in ensuring all other cells are filled accurately based on reachable neighbors.

Think of this scenario as a game where you can only enter a park from its gates. If one gate is blocked (like having a hole in our grid), the only way to reach certain areas is through the remaining gates. If you're at the entrance, there’s just you—no one else can join until you step forward, and this simplicity creates a rule for entering the park.

So, how do we deal with holes in this setup? That is easy, we just say, that whenever there is a hole at a given point we just declare parts of ((Refer Time: 11:52)) be 0. ... Then we have the bottom row left column and the origin as base cases.

This chunk outlines how to handle situations where there are 'holes' or obstacles on the grid—specific points where movement is not possible. If a position on the grid contains a hole, we assign it a path value of zero, indicating that no paths can pass through there. Consequently, this zero value will impact calculations for neighboring points; paths leading to these holes will not count, effectively propagating the zero value to neighboring calculations. The key takeaway is that these holes impact the overall path count by blocking potential routes.

Imagine trying to walk through a garden, but some areas are fenced off (the holes). If you can't walk through those fenced-off sections, then the paths leading to those sections can't exist either. The fences (holes) will result in fewer possible routes to reach your destination as you have to navigate around them.

So, the difficulty with this calculation is the same as involved with the Fibonacci, which is, that if I have a particular calculation, say for example, supposing we start a recursive calculation at (5,10), then this will ask for (4,10) and (5,9). ... if it is a hole, we just ignore it.

This chunk addresses the drawback of calculating paths recursively, similar to the Fibonacci sequence. Here, we see that a recursive call for a coordinate repeatedly accesses the same previous coordinates, leading to redundant calculations. This results in inefficiency because the same states are computed multiple times. To resolve this issue, techniques like memoization are introduced, which ensures that each unique path calculation is stored and only computed once, thereby reducing overall computational load.

Consider a scenario where someone is trying to save a cooking recipe. If they keep writing down the same steps every time they want to refer to the recipe, it takes longer each time to cook. If instead, they jot down the entire recipe once and refer to that, they save time and effort during each cooking session. This is analogous to memoization; once a result is known, it doesn’t need to be recalculated.

So, how would we use dynamic programming on the grid? ... So, if it is not a hole, it depends on its two neighbors.

This segment introduces dynamic programming as a strategic method of computing paths. Unlike the recursive approach, dynamic programming calculates paths in a more systematic manner, filling up all values based on their dependencies in a directed acyclic graph (DAG). It begins at a known starting point (typically (0,0)) and iteratively computes values for every cell, making sure to integrate values only from the allowable neighbors. This process ensures more efficient calculations while navigating around obstacles.

Think of building a Lego structure. Instead of constructing each piece individually and worrying about how each connects repeatedly, you lay out the blocks step-by-step following a plan. As each section is completed, it becomes easier to see how it all fits together, leading to an organized and efficient way of building, much like dynamic programming organizes and computes paths.

So, finally, before we conclude, let us just look at an instructive illustration of the difference between memoization and dynamic programming. ... So, therefore, the memo table will have a linear number of entries.

This concluding part highlights the distinction between memoization and dynamic programming. Memoization is seen as a more straightforward approach that retains previously calculated results to avoid redundant calculations, while dynamic programming globally computes all values through a structured methodology. The downside of memoization is that it may only cover values that are necessary as per immediate requests and may miss calculating dependencies due to its recursive nature. In contrast, the dynamic programming approach ensures all necessary computations are made, even if some values are ultimately unneeded. Although dynamic programming might look inefficient, it often yields better results in the long run.

Imagine someone trying to write a book. If they keep rewriting the same plot every time they talk about it (memoization), they may only record their best parts and skip around. However, a good author outlines the entire story (dynamic programming), even if certain sections aren’t revisited. This results in a cohesive narrative that flows, capturing all details, unlike sporadic revisions which may miss critical connections.

--