Traverse a given Matrix using Recursion
Last Updated :
09 Mar, 2023
Given a matrix arr of size N x M, the task is to traverse this matrix using recursion.
Examples:
Input: arr[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9
Input: M[][] = {{11, 12, 13},
{14, 15, 16},
{17, 18, 19}}
Output: 11, 12, 13, 14, 15, 16, 17, 18, 19
Approach:
- Check If the current position is in the bottom-right corner of the matrix
- Print the value at that position
- End the recursion
- Print the value at the current position
- Check If the end of the current row has not been reached
- Check If the end of the current column has been reached
- Move down to the next row
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
const int N = 3;
const int M = 3;
void traverse(int arr[][M], int i, int j)
{
if (i == N - 1 && j == M - 1) {
cout << arr[i][j] << endl;
return;
}
cout << arr[i][j] << ", ";
if (j < M - 1) {
traverse(arr, i, j + 1);
}
else if (i < N - 1) {
traverse(arr, i + 1, 0);
}
}
int main()
{
int arr[N][M]
= { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
traverse(arr, 0, 0);
return 0;
}
|
Java
public class MatrixTraversal {
private static final int N = 3;
private static final int M = 3;
private static void traverse(int[][] arr, int i, int j) {
if (i == N - 1 && j == M - 1) {
System.out.println(arr[i][j]);
return;
}
System.out.print(arr[i][j] + ", ");
if (j < M - 1) {
traverse(arr, i, j + 1);
}
else if (i < N - 1) {
traverse(arr, i + 1, 0);
}
}
public static void main(String[] args) {
int[][] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
traverse(arr, 0, 0);
}
}
|
Python3
N = 3
M = 3
def traverse(arr, i, j):
if i == N - 1 and j == M - 1:
print(arr[i][j])
return
print(arr[i][j], end=", ")
if j < M - 1:
traverse(arr, i, j + 1)
elif i < N - 1:
traverse(arr, i + 1, 0)
arr = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
traverse(arr, 0, 0)
|
C#
using System;
public class Program
{
private const int N = 3;
private const int M = 3;
private static void Traverse(int[,] arr, int i, int j)
{
if (i == N - 1 && j == M - 1)
{
Console.WriteLine(arr[i, j]);
return;
}
Console.Write($"{arr[i, j]}, ");
if (j < M - 1)
{
Traverse(arr, i, j + 1);
}
else if (i < N - 1)
{
Traverse(arr, i + 1, 0);
}
}
public static void Main()
{
int[,] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
Traverse(arr, 0, 0);
}
}
|
Javascript
const N = 3;
const M = 3;
let ans="";
function traverse(arr, i, j)
{
if (i === N - 1 && j === M - 1)
{
ans =ans + arr[i][j];
return;
}
ans =ans + arr[i][j]+", ";
if (j < M - 1)
{
traverse(arr, i, j + 1);
}
else if (i < N - 1)
{
traverse(arr, i + 1, 0);
}
}
const arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
traverse(arr, 0, 0); console.log(ans);
|
Output
1, 2, 3, 4, 5, 6, 7, 8, 9
Time Complexity: O(N * M)
Auxiliary Space: O(M), because of recursive calling
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...