- Given the length of Row and Column of a 2D matrix.
- Starting from origin (0,0), find the maximum number of Paths one can take to reach the last index.
- Allowed ways to move => Right and Bottom.

Example:

- Let, row's length and column length be (2, 2)
- Starting from (0,0) one should reach (1,1)
- So the number of paths for that are: 2

Path 1: (0,0) -> (0,1) -> (1,1) Path 2: (0,0) -> (1,0) -> (1,1)

- We are allowed to traverse in two ways Down and Right for every Index. So this is a pattern.

- While we iterate we need to be careful about the ending index's count and so we should handle those cases.
- Path is 0 when the input is less than 1 for either row or column.

We found a pattern to go through for every index we can choose to solve with iteration / recursion.

Here we will solve it through RECURSION!

```
const num_of_paths = findMaxPathSrcToDes(3, 3);
console.log('Number of Paths', num_of_paths);
```

We call `findMaxPathSrcToDes`

and pass row length and column length and log it.

```
function findMaxPathSrcToDes(rows, cols) {
// Initial rows and columns to begin with.0,0 is the first row and col index we are choosing
return findMaxPath(0, 0, rows - 1, cols - 1);
}
```

`findMaxPathSrcToDes`

function accepts the row length and column length from the user.- It then returns the output from
`findMaxPath`

function to which we pass the origin which is (0,0) and destination index(rows -1, cols - 1). - We can modify this origin and destination index to user defined positions by accepting those, so that we can identify the number of paths any index from any index.

`findMaxPath`

function takes in 4 params and outputs the number of path.

`currentRow`

- Which indicates the current index's Row that is being processed.`currentRow`

- Which indicates the current index's Column that is being processed.`destRow`

- Destination row index`destCol`

- Destination column index

In any Recursive solution, start with writing the **base conditions or Exit conditions.**

*So, what is a Base condition or Exit condition?*

It is basically the case on satisfying which our algorithm should terminate. So, let's formulate one.

- When
`currentRow > destRow`

(In this case it indicates that the`currentRow`

count has gone out of bound). - When
`currentColumn > destCol`

(In this case it indicates that the`currentColumn`

count has gone out of bound). So we return '0' in both the cases.

```
function findMaxPath(currentRow, currentColumn, destRow, destCol) {
// Base condition
if (currentRow > destRow || currentColumn > destCol) {
return 0;
}
}
```

- if
`currentRow === destRow`

or`currentColumn === destCol`

this indicates that we have reached the destination index so we return`1`

to indicate a successful path.

```
if (currentRow === destRow && currentColumn === destCol) {
return 1;
}
```

- For each index there are two ways 1.Right and 2.Down
- So, we have to recurse in both ways and add the path formed from each ways.
- We call
`findMaxPath`

by incrementing`currentRow`

by 1. - Then again by incrementing
`currentColumn`

by 1 and adding the outputs of these two and return them.

```
const pathsInRows = findMaxPath(currentRow + 1, currentColumn, destRow, destCol);
const pathsInColums = findMaxPath(currentRow, currentColumn + 1, destRow, destCol);
return (pathsInRows + pathsInColums);
```

CodePen link here

Next Step:

- You could try printing all possible paths along with count

A blog by Dhilip kumar