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.

New Comment