**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