Posted on by Kalkicode
Code Recursion

# Traverse a given Matrix using Recursion

Traversing a matrix means visiting each element of the matrix exactly once, either row-wise or column-wise or in some other order, depending on the requirements. Traversing a matrix using recursion means visiting each element of the matrix by calling a recursive function that traverses the neighboring elements of the current element until all the elements have been visited.

The given problem is to traverse a given matrix using recursion. In this problem, we are provided with a 2D matrix of size R x C, where R represents the number of rows and C represents the number of columns. Our goal is to print all the elements of the matrix in a specific order using recursion.

## Problem Statement

We are given a 2D matrix `matrix[R][C]`, and we need to display all its elements in a row-wise manner using recursion.

## Example

Let's understand the problem with a simple example. Consider the following matrix:

``````[[1, 9, 8, 3, 7] ,
[3, -1, 5, 3, 8] ,
[1, 3, 4, 6, 11] ,
[0, 8, 8, 6, 2] ,
[1, 3, 4, 5, 10] ,
[3, 5, 7, 2, 8]]
Result :
Matrix Elements
1   9   8   3   7
3   -1   5   3   8
1   3   4   6   11
0   8   8   6   2
1   3   4   5   10
3   5   7   2   8
``````

## Standard Pseudocode

``````function show_element(r, c, i, j, matrix[R][C]):
if i >= r:
return
else if j >= c:
print newline
show_element(r, c, i+1, 0, matrix)
else:
print matrix[i][j]
show_element(r, c, i, j+1, matrix)

function print_matrix(matrix[R][C]):
print "Matrix Elements"
show_element(R, C, 0, 0, matrix)
print newline

``````

## Algorithm Explanation

1. The function `show_element` takes six parameters: `r` (total rows), `c` (total columns), `i` (current row index), `j` (current column index), and the 2D `matrix`.
2. If `i >= r`, it means we have already executed all rows, so we return from the function.
3. If `j >= c`, it means we have reached the end of the current row, so we print a newline and call the `show_element` function recursively for the next row (i.e., `i+1`) and the first column (i.e., `0`).
4. Otherwise, we are still within the same row, so we print the element `matrix[i][j]`, and then we call the `show_element` function recursively for the same row (i.e., `i`) and the next column (i.e., `j+1`).
5. The function `print_matrix` is a helper function that prints the header "Matrix Elements" and calls the `show_element` function with initial values (`i=0`, `j=0`) to start the recursion.

## Explanation with Example

Using the provided example matrix, let's go through the recursion step by step:

1. `show_element(6, 5, 0, 0, matrix)` is called from `print_matrix`.
2. `i=0`, `j=0`, and `matrix[0][0] = 1`, so `1` is printed.
3. `show_element(6, 5, 0, 1, matrix)` is called.
4. `i=0`, `j=1`, and `matrix[0][1] = 9`, so `9` is printed.
5. This process continues until all elements are printed in the row.
6. Once the first row is printed, `show_element` is called for the next row, and this continues until all rows are printed.

## Program Solution

``````// C Program
// Traverse a given Matrix using Recursion
#include <stdio.h>
#include <stdlib.h>
#define R 6
#define C 5
// Recursively, display elements of given matrix
void show_element(int r,int c, int i,int j,int matrix[R][C])
{
if(i >= r)
{
// When has been already executed all rows
return;
}
else if(j >= c)
{
// Change row
printf("\n");
// visit to next row
show_element(r,c,i+1,0,matrix);
}
else
{
// print element
printf("  %d",matrix[i][j]);

// visit to next column
show_element(r,c,i,j+1,matrix);
}
}

// Handles the request of display matrix elements
void print_matrix(int matrix[R][C])
{
printf("  Matrix Elements \n");
show_element(R,C,0,0,matrix);
printf("\n");
}

int main()
{

// Define matrix of integer elements
int matrix[R][C] =
{
{1, 9, 8 , 3  , 7},
{3, -1, 5 , 3 , 8},
{1, 3,  4,  6 , 11},
{0, 8,  8,  6 , 2},
{1, 3,  4,  5 , 10},
{3, 5,  7,  2 , 8}
};

print_matrix(matrix);

return 0;
}``````

#### Output

``````  Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````/*
Java program
Traverse a given Matrix using Recursion
*/
// Define TreeNode
class MyMatrix
{
// Recursively, display elements of given matrix
public void show_element(int r, int c, int i, int j, int[][] matrix)
{
if (i >= r)
{
// When has been already executed all rows
return;
}
else if (j >= c)
{
// Change row
System.out.print("\n");
// visit to next row
show_element(r, c, i + 1, 0, matrix);
}
else
{
// print element
System.out.print("  " + matrix[i][j]);
// visit to next column
show_element(r, c, i, j + 1, matrix);
}
}
// Handles the request of display matrix elements
public void print_matrix(int[][] matrix)
{
// Get the size
int row = matrix.length;
int col = matrix[0].length;
System.out.print(" Matrix Elements \n");
show_element(row, col, 0, 0, matrix);
System.out.print("\n");
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
// Define matrix of integer elements
int[][] matrix = {
{ 1 , 9 , 8 , 3 , 7  } ,
{ 3 , -1 , 5 , 3 , 8 } ,
{ 1 , 3 , 4 , 6 , 11 } ,
{ 0 , 8 , 8 , 6 , 2  } ,
{ 1 , 3 , 4 , 5 , 10 } ,
{ 3 , 5 , 7 , 2 , 8  }
};
obj.print_matrix(matrix);
}
}``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````// Include header file
#include <iostream>
#define R 6
#define C 5

using namespace std;
/*
C++ program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
class MyMatrix
{
public:
//  Recursively, display elements of given matrix
void show_element(int i, int j, int matrix [R][C])
{
//  When has been already executed all rows
if (i >= R)
{
return;
}
else if (j >= C)
{
//  Change row
cout << "\n";
//  visit to next row
this->show_element( i + 1, 0, matrix);
}
else
{
//  print element
cout << "  " << matrix[i][j];
//  visit to next column
this->show_element(i, j + 1, matrix);
}
}
//  Handles the request of display matrix elements
void print_matrix(int matrix[R][C])
{
//  Get the size
cout << " Matrix Elements \n";
this->show_element( 0, 0, matrix);
cout << "\n";
}
};
int main()
{
MyMatrix obj = MyMatrix();
//  Define matrix of integer elements
int matrix[R][C] = {
{1, 9, 8 , 3  , 7},
{3, -1, 5 , 3 , 8},
{1, 3,  4,  6 , 11},
{0, 8,  8,  6 , 2},
{1, 3,  4,  5 , 10},
{3, 5,  7,  2 , 8}
};
obj.print_matrix(matrix);
return 0;
}``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````// Include namespace system
using System;
/*
C# program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
public class MyMatrix
{
//  Recursively, display elements of given matrix
public void show_element(int r, int c, int i, int j, int[,] matrix)
{
//  When has been already executed all rows
if (i >= r)
{
return;
}
else if (j >= c)
{
//  Change row
Console.Write("\n");
//  visit to next row
show_element(r, c, i + 1, 0, matrix);
}
else
{
//  print element
Console.Write("  " + matrix[i,j]);
//  visit to next column
show_element(r, c, i, j + 1, matrix);
}
}
//  Handles the request of display matrix elements
public void print_matrix(int[,] matrix)
{
//  Get the size
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
Console.Write(" Matrix Elements \n");
show_element(row, col, 0, 0, matrix);
Console.Write("\n");
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
//  Define matrix of integer elements
int[,] matrix = {
{1, 9, 8 , 3  , 7},
{3, -1, 5 , 3 , 8},
{1, 3,  4,  6 , 11},
{0, 8,  8,  6 , 2},
{1, 3,  4,  5 , 10},
{3, 5,  7,  2 , 8}
};
obj.print_matrix(matrix);
}
}``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````<?php
/*
Php program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
class MyMatrix
{
//  Recursively, display elements of given matrix
public	function show_element(\$r, \$c, \$i, \$j, & \$matrix)
{
//  When has been already executed all rows
if (\$i >= \$r)
{
return;
}
else if (\$j >= \$c)
{
//  Change row
echo "\n";
//  visit to next row
\$this->show_element(\$r, \$c, \$i + 1, 0, \$matrix);
}
else
{
//  print element
echo "  ". \$matrix[\$i][\$j];
//  visit to next column
\$this->show_element(\$r, \$c, \$i, \$j + 1, \$matrix);
}
}
//  Handles the request of display matrix elements
public	function print_matrix( & \$matrix)
{
//  Get the size
\$row = count(\$matrix);
\$col = count(\$matrix[0]);
echo " Matrix Elements \n";
\$this->show_element(\$row, \$col, 0, 0, \$matrix);
echo "\n";
}
}

function main()
{
\$obj = new MyMatrix();
//  Define matrix of integer elements
\$matrix = array(
array(1, 9, 8, 3, 7),
array(3, -1, 5, 3, 8),
array(1, 3, 4, 6, 11),
array(0, 8, 8, 6, 2),
array(1, 3, 4, 5, 10),
array(3, 5, 7, 2, 8)
);
\$obj->print_matrix(\$matrix);
}
main();``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````/*
Node Js program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
class MyMatrix
{
//  Recursively, display elements of given matrix
show_element(r, c, i, j, matrix)
{
//  When has been already executed all rows
if (i >= r)
{
return;
}
else if (j >= c)
{
//  Change row
process.stdout.write("\n");
//  visit to next row
this.show_element(r, c, i + 1, 0, matrix);
}
else
{
//  print element
process.stdout.write("  " + matrix[i][j]);
//  visit to next column
this.show_element(r, c, i, j + 1, matrix);
}
}
//  Handles the request of display matrix elements
print_matrix(matrix)
{
//  Get the size
var row = matrix.length;
var col = matrix[0].length;
process.stdout.write(" Matrix Elements \n");
this.show_element(row, col, 0, 0, matrix);
process.stdout.write("\n");
}
}

function main()
{
var obj = new MyMatrix();
//  Define matrix of integer elements
var matrix = [
[1, 9, 8, 3, 7] ,
[3, -1, 5, 3, 8] ,
[1, 3, 4, 6, 11] ,
[0, 8, 8, 6, 2] ,
[1, 3, 4, 5, 10] ,
[3, 5, 7, 2, 8]
];
obj.print_matrix(matrix);
}
main();``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````#  Python 3 program
#  Traverse a given Matrix using Recursion

#  Define TreeNode
class MyMatrix :
#  Recursively, display elements of given matrix
def show_element(self, r, c, i, j, matrix) :
if (i >= r) :
#  When has been already executed all rows
return

elif(j >= c) :
#  Change row
print("\n", end = "")
#  visit to next row
self.show_element(r, c, i + 1, 0, matrix)
else :
#  print element
print("  ", matrix[i][j], end = "")
#  visit to next column
self.show_element(r, c, i, j + 1, matrix)

#  Handles the request of display matrix elements
def print_matrix(self, matrix) :
#  Get the size
row = len(matrix)
col = len(matrix[0])
print(" Matrix Elements \n", end = "")
self.show_element(row, col, 0, 0, matrix)
print("\n", end = "")

def main() :
obj = MyMatrix()
#  Define matrix of integer elements
matrix = [
[1, 9, 8, 3, 7] ,
[3, -1, 5, 3, 8] ,
[1, 3, 4, 6, 11] ,
[0, 8, 8, 6, 2] ,
[1, 3, 4, 5, 10] ,
[3, 5, 7, 2, 8]
]
obj.print_matrix(matrix)

if __name__ == "__main__": main()``````

#### Output

`````` Matrix Elements
1   9   8   3   7
3   -1   5   3   8
1   3   4   6   11
0   8   8   6   2
1   3   4   5   10
3   5   7   2   8
``````
``````#  Ruby program
#  Traverse a given Matrix using Recursion

#  Define TreeNode
class MyMatrix
#  Recursively, display elements of given matrix
def show_element(r, c, i, j, matrix)
if (i >= r)
#  When has been already executed all rows
return
elsif(j >= c)
#  Change row
print("\n")
#  visit to next row
self.show_element(r, c, i + 1, 0, matrix)
else
#  print element
print("  ", matrix[i][j])
#  visit to next column
self.show_element(r, c, i, j + 1, matrix)
end

end

#  Handles the request of display matrix elements
def print_matrix(matrix)
#  Get the size
row = matrix.length
col = matrix[0].length
print(" Matrix Elements \n")
self.show_element(row, col, 0, 0, matrix)
print("\n")
end

end

def main()
obj = MyMatrix.new()
#  Define matrix of integer elements
matrix = [
[1, 9, 8, 3, 7] , [3, -1, 5, 3, 8] , [1, 3, 4, 6, 11] , [0, 8, 8, 6, 2] , [1, 3, 4, 5, 10] , [3, 5, 7, 2, 8]
]
obj.print_matrix(matrix)
end

main()``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8

``````
``````/*
Scala program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
class MyMatrix
{
//  Recursively, display elements of given matrix
def show_element(r: Int, c: Int, i: Int, j: Int, matrix: Array[Array[Int]]): Unit = {
//  When has been already executed all rows
if (i >= r)
{
return;
}
else if (j >= c)
{
//  Change row
print("\n");
//  visit to next row
this.show_element(r, c, i + 1, 0, matrix);
}
else
{
//  print element
print("  " + matrix(i)(j));
//  visit to next column
this.show_element(r, c, i, j + 1, matrix);
}
}
//  Handles the request of display matrix elements
def print_matrix(matrix: Array[Array[Int]]): Unit = {
//  Get the size
var row: Int = matrix.length;
var col: Int = matrix(0).length;
print(" Matrix Elements \n");
this.show_element(row, col, 0, 0, matrix);
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
//  Define matrix of integer elements
var matrix: Array[Array[Int]] = Array(
Array(1, 9, 8, 3, 7),
Array(3, -1, 5, 3, 8),
Array(1, 3, 4, 6, 11),
Array(0, 8, 8, 6, 2),
Array(1, 3, 4, 5, 10),
Array(3, 5, 7, 2, 8)
);
obj.print_matrix(matrix);
}
}``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````
``````/*
Swift 4 program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
class MyMatrix
{
//  Recursively, display elements of given matrix
func show_element(_ r: Int, _ c: Int, _ i: Int, _ j: Int, _ matrix: [
[Int]
])
{
//  When has been already executed all rows
if (i >= r)
{
return;
}
else if (j >= c)
{
//  Change row
print("\n", terminator: "");
//  visit to next row
self.show_element(r, c, i + 1, 0, matrix);
}
else
{
//  print element
print("  ", matrix[i][j], terminator: "");
//  visit to next column
self.show_element(r, c, i, j + 1, matrix);
}
}
//  Handles the request of display matrix elements
func print_matrix(_ matrix: [
[Int]
])
{
//  Get the size
let row: Int = matrix.count;
let col: Int = matrix[0].count;
print(" Matrix Elements ");
self.show_element(row, col, 0, 0, matrix);
print(terminator: "\n");
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
//  Define matrix of integer elements
let matrix: [[Int]] = [[1, 9, 8, 3, 7] ,
[3, -1, 5, 3, 8] ,
[1, 3, 4, 6, 11] ,
[0, 8, 8, 6, 2] ,
[1, 3, 4, 5, 10] ,
[3, 5, 7, 2, 8]
];
obj.print_matrix(matrix);
}
main();``````

#### Output

`````` Matrix Elements
1   9   8   3   7
3   -1   5   3   8
1   3   4   6   11
0   8   8   6   2
1   3   4   5   10
3   5   7   2   8
``````
``````/*
Kotlin program
Traverse a given Matrix using Recursion
*/
//  Define TreeNode
class MyMatrix
{
//  Recursively, display elements of given matrix
fun show_element(r: Int, c: Int, i: Int, j: Int, matrix: Array<Array<Int>> ): Unit
{
//  When has been already executed all rows
if (i >= r)
{
return;
}
else
if (j >= c)
{
//  Change row
print("\n");
//  visit to next row
this.show_element(r, c, i + 1, 0, matrix);
}
else
{
//  print element
print("  " + matrix[i][j]);
//  visit to next column
this.show_element(r, c, i, j + 1, matrix);
}
}
//  Handles the request of display matrix elements
fun print_matrix(matrix: Array < Array < Int >> ): Unit
{
//  Get the size
var row: Int = matrix.count();
var col: Int = matrix[0].count();
print(" Matrix Elements \n");
this.show_element(row, col, 0, 0, matrix);
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
var obj: MyMatrix = MyMatrix();
//  Define matrix of integer elements
var matrix: Array<Array<Int>> =
arrayOf(
arrayOf(1, 9, 8, 3, 7),
arrayOf(3, -1, 5, 3, 8),
arrayOf(1, 3, 4, 6, 11),
arrayOf(0, 8, 8, 6, 2),
arrayOf(1, 3, 4, 5, 10),
arrayOf(3, 5, 7, 2, 8)
);
obj.print_matrix(matrix);
}``````

#### Output

`````` Matrix Elements
1  9  8  3  7
3  -1  5  3  8
1  3  4  6  11
0  8  8  6  2
1  3  4  5  10
3  5  7  2  8
``````

## Time Complexity

The time complexity of this recursive function can be analyzed as follows:

• Each element of the matrix is printed exactly once.
• The matrix has R x C elements.
• Therefore, the time complexity of the recursion is O(R * C).

## Finally

In this article, we discussed how to traverse a given matrix using recursion. We explained the problem, provided a standard pseudocode, and discussed the algorithm step by step with the help of an example. We also provided a resultant output and analyzed the time complexity of the given code. Recursion is a powerful technique for solving problems, but it is essential to handle base cases properly to ensure the termination of the recursion and prevent stack overflow errors.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post