 # Depth-First Search (DFS) in 2D Matrix/2D-Array – Recursive Solution

Objective: Given a two-dimensional array or matrix, Do the depth-First Search (DFS) to print the elements of the given matrix. Implement the Depth-first traversal in a recursive manner.

Example:

```int [][] grid = new int[][] {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output:
Depth-First Traversal:
1 5 9 13 14 10 6 2 3 7 11 15 16 12 8 4
```

Approach – Use Recursion

As we know stack is used for DFS.

• Initialize stack.
• Initialize 2d boolean array, the same size as the original array. This will help us in avoiding traversal to go in loops.
• Make a call to recursive function DFSUtil with row=0, column =0 and visited[] array.

In DFSutil Function

check if row and column indexes are within the range of given matrix and marked false in the visited[] array, if not then return from the function. If indexes are valid and not visited then print the element. Mark the element in the visited array. Make a recursive call to left(column-1), right(column+1), down(row+1) and up(row+1) from the current element position.

See the code below for more understanding.

Complete Code:

Output:

```Depth-First Traversal:
1 5 9 13 14 10 6 2 3 7 11 15 16 12 8 4
```