Display Diagonally Bottom-Up matrix using Recursion
The given problem requires displaying the elements of a matrix diagonally from the bottom-up using recursion. The input is a square matrix of size N x N, and the output should be the elements of the matrix displayed diagonally from the bottom-left to the top-right.
Problem Statement
Given a square matrix, we need to display its elements diagonally from the bottom-left to the top-right using recursion.
Example
Consider the following matrix:
1 2 3 4 5 6
22 23 24 25 26 7
21 36 37 38 27 8
20 35 42 39 28 9
19 34 41 40 29 10
18 33 32 31 30 11
The output of the program will be:
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
Pseudocode
// Function to print diagonal elements starting from (row, col)
print_diagonally(matrix, row, col):
// Base case: If row or col is outside matrix boundaries, return
if row >= N or col >= N:
return
// Print the element at (row, col)
print matrix[row][col]
// Recursively call print_diagonally for the next diagonal element
print_diagonally(matrix, row + 1, col + 1)
// Function to recursively handle the request of printing diagonal elements
print_element(matrix, i):
// Base case: If i is greater than or equal to N, return
if i >= N:
return
// For i = 0, print the first middle layer (main diagonal)
if i == 0:
print_diagonally(matrix, i, 0)
else:
// For other diagonal layers, print bottom diagonal and top diagonal
print_diagonally(matrix, i, 0)
print_diagonally(matrix, 0, i)
// Recursively call print_element for the next diagonal layer (i+1)
print_element(matrix, i + 1)
// Main function
main():
// Initialize the matrix with N x N elements
matrix[N][N] = {...}
// Call print_element to start the diagonal printing process with i=0
print_element(matrix, 0)
Algorithm Explanation
- We have two main functions,
print_diagonally
andprint_element
, to handle the recursion for printing diagonal elements. - The
print_diagonally
function prints the diagonal elements starting from a given position(row, col)
. - The
print_element
function handles the recursive requests for printing diagonal elements for each diagonal layer. - The
print_element
function starts withi=0
, which means it prints the first middle layer (the main diagonal) using theprint_diagonally
function. - For each subsequent diagonal layer, the
print_element
function callsprint_diagonally
twice: once for the bottom diagonal and once for the top diagonal, by adjusting the starting positions accordingly. - The recursion continues until all diagonal layers are printed.
- In the main function, we initialize the matrix and call
print_element
withi=0
to start the diagonal printing process.
Code Solution
Here given code implementation process.
// C Program
// Display Diagonally Bottom-Up matrix using Recursion
#include <stdio.h>
#define N 6
// Print diagonally element
void print_diagonally(int matrix[N][N],int row,int col)
{
if(row >= N || col >= N)
{
printf("\n");
return;
}
printf(" %d",matrix[row][col]);
//visit next row and column
print_diagonally(matrix,row+1, col+1);
}
// Recursively handles the request of printing diagonal elements
void print_element(int matrix[N][N],int i)
{
if(i >= N)
{
return;
}
if(i == 0)
{
// First middle layer (First diagonal layer)
print_diagonally(matrix,i,0);
}
else
{
// Bottom diagonal
print_diagonally(matrix,i,0);
// Top diagonal
print_diagonally(matrix,0,i);
}
print_element(matrix,i+1);
}
int main()
{
int matrix[N][N] =
{
{1 , 2 , 3 , 4 , 5 , 6} ,
{22 , 23 , 24 , 25 , 26 , 7} ,
{21 , 36 , 37 , 38 , 27 , 8} ,
{20 , 35 , 42 , 39 , 28 , 9} ,
{19 , 34 , 41 , 40 , 29 , 10} ,
{18 , 33 , 32 , 31 , 30 , 11}
};
print_element(matrix,0);
return 0;
}
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
/*
Java Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
// Print diagonally element
public void print_diagonally(int[][] matrix, int row, int col, int size)
{
if (row >= size || col >= size)
{
System.out.print("\n");
return;
}
System.out.print(" " + matrix[row][col]);
//visit next row and column
print_diagonally(matrix, row + 1, col + 1 ,size);
}
// Recursively handles the request of printing diagonal elements
public void print_element(int[][] matrix, int i, int size)
{
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
print_diagonally(matrix, i, 0 ,size);
}
else
{
// Bottom diagonal
print_diagonally(matrix, i, 0 ,size);
// Top diagonal
print_diagonally(matrix, 0, i ,size);
}
print_element(matrix, i + 1,size);
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
int[][] matrix =
{
{1 , 2 , 3 , 4 , 5 , 6} ,
{22 , 23 , 24 , 25 , 26 , 7} ,
{21 , 36 , 37 , 38 , 27 , 8} ,
{20 , 35 , 42 , 39 , 28 , 9} ,
{19 , 34 , 41 , 40 , 29 , 10} ,
{18 , 33 , 32 , 31 , 30 , 11}
};
int size = matrix.length;
obj.print_element(matrix,0,size);
}
}
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
// Include header file
#include <iostream>
#define N 6
using namespace std;
/*
C++ Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
public:
// Print diagonally element
void print_diagonally(int matrix[N][N], int row, int col, int size)
{
if (row >= size || col >= size)
{
cout << "\n";
return;
}
cout << " " << matrix[row][col];
// visit next row and column
this->print_diagonally(matrix, row + 1, col + 1, size);
}
// Recursively handles the request of printing diagonal elements
void print_element(int matrix[N][N], int i, int size)
{
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
this->print_diagonally(matrix, i, 0, size);
}
else
{
// Bottom diagonal
this->print_diagonally(matrix, i, 0, size);
// Top diagonal
this->print_diagonally(matrix, 0, i, size);
}
this->print_element(matrix, i + 1, size);
}
};
int main()
{
MyMatrix obj = MyMatrix();
int matrix[N][N] =
{
{1 , 2 , 3 , 4 , 5 , 6} ,
{22 , 23 , 24 , 25 , 26 , 7} ,
{21 , 36 , 37 , 38 , 27 , 8} ,
{20 , 35 , 42 , 39 , 28 , 9} ,
{19 , 34 , 41 , 40 , 29 , 10} ,
{18 , 33 , 32 , 31 , 30 , 11}
};
obj.print_element(matrix, 0, N);
return 0;
}
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
// Include namespace system
using System;
/*
C# Program
Display Diagonally Bottom-Up matrix using Recursion
*/
public class MyMatrix
{
// Print diagonally element
public void print_diagonally(int[,] matrix, int row, int col, int size)
{
if (row >= size || col >= size)
{
Console.Write("\n");
return;
}
Console.Write(" " + matrix[row,col]);
// visit next row and column
print_diagonally(matrix, row + 1, col + 1, size);
}
// Recursively handles the request of printing diagonal elements
public void print_element(int[,] matrix, int i, int size)
{
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
print_diagonally(matrix, i, 0, size);
}
else
{
// Bottom diagonal
print_diagonally(matrix, i, 0, size);
// Top diagonal
print_diagonally(matrix, 0, i, size);
}
print_element(matrix, i + 1, size);
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
int[,] matrix =
{
{1 , 2 , 3 , 4 , 5 , 6} ,
{22 , 23 , 24 , 25 , 26 , 7} ,
{21 , 36 , 37 , 38 , 27 , 8} ,
{20 , 35 , 42 , 39 , 28 , 9} ,
{19 , 34 , 41 , 40 , 29 , 10} ,
{18 , 33 , 32 , 31 , 30 , 11}
};
int size = matrix.GetLength(0);
obj.print_element(matrix, 0, size);
}
}
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
<?php
/*
Php Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
// Print diagonally element
public function print_diagonally( & $matrix, $row, $col, $size)
{
if ($row >= $size || $col >= $size)
{
echo "\n";
return;
}
echo " ". $matrix[$row][$col];
// visit next row and column
$this->print_diagonally($matrix, $row + 1, $col + 1, $size);
}
// Recursively handles the request of printing diagonal elements
public function print_element( & $matrix, $i, $size)
{
if ($i >= $size)
{
return;
}
if ($i == 0)
{
// First middle layer (First diagonal layer)
$this->print_diagonally($matrix, $i, 0, $size);
}
else
{
// Bottom diagonal
$this->print_diagonally($matrix, $i, 0, $size);
// Top diagonal
$this->print_diagonally($matrix, 0, $i, $size);
}
$this->print_element($matrix, $i + 1, $size);
}
}
function main()
{
$obj = new MyMatrix();
$matrix = array(
array(1, 2, 3, 4, 5, 6),
array(22, 23, 24, 25, 26, 7),
array(21, 36, 37, 38, 27, 8),
array(20, 35, 42, 39, 28, 9),
array(19, 34, 41, 40, 29, 10),
array(18, 33, 32, 31, 30, 11)
);
$size = count($matrix);
$obj->print_element($matrix, 0, $size);
}
main();
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
/*
Node Js Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
// Print diagonally element
print_diagonally(matrix, row, col, size)
{
if (row >= size || col >= size)
{
process.stdout.write("\n");
return;
}
process.stdout.write(" " + matrix[row][col]);
// visit next row and column
this.print_diagonally(matrix, row + 1, col + 1, size);
}
// Recursively handles the request of printing diagonal elements
print_element(matrix, i, size)
{
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
this.print_diagonally(matrix, i, 0, size);
}
else
{
// Bottom diagonal
this.print_diagonally(matrix, i, 0, size);
// Top diagonal
this.print_diagonally(matrix, 0, i, size);
}
this.print_element(matrix, i + 1, size);
}
}
function main()
{
var obj = new MyMatrix();
var matrix = [
[1, 2, 3, 4, 5, 6] ,
[22, 23, 24, 25, 26, 7] ,
[21, 36, 37, 38, 27, 8] ,
[20, 35, 42, 39, 28, 9] ,
[19, 34, 41, 40, 29, 10] ,
[18, 33, 32, 31, 30, 11]
];
var size = matrix.length;
obj.print_element(matrix, 0, size);
}
main();
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
# Python 3 Program
# Display Diagonally Bottom-Up matrix using Recursion
class MyMatrix :
# Print diagonally element
def print_diagonally(self, matrix, row, col, size) :
if (row >= size or col >= size) :
print("\n", end = "")
return
print(" ", matrix[row][col], end = "")
# visit next row and column
self.print_diagonally(matrix, row + 1, col + 1, size)
# Recursively handles the request of printing diagonal elements
def print_element(self, matrix, i, size) :
if (i >= size) :
return
if (i == 0) :
# First middle layer (First diagonal layer)
self.print_diagonally(matrix, i, 0, size)
else :
# Bottom diagonal
self.print_diagonally(matrix, i, 0, size)
# Top diagonal
self.print_diagonally(matrix, 0, i, size)
self.print_element(matrix, i + 1, size)
def main() :
obj = MyMatrix()
matrix = [
[1, 2, 3, 4, 5, 6] ,
[22, 23, 24, 25, 26, 7] ,
[21, 36, 37, 38, 27, 8] ,
[20, 35, 42, 39, 28, 9] ,
[19, 34, 41, 40, 29, 10] ,
[18, 33, 32, 31, 30, 11]
]
size = len(matrix)
obj.print_element(matrix, 0, size)
if __name__ == "__main__": main()
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
# Ruby Program
# Display Diagonally Bottom-Up matrix using Recursion
class MyMatrix
# Print diagonally element
def print_diagonally(matrix, row, col, size)
if (row >= size || col >= size)
print("\n")
return
end
print(" ", matrix[row][col])
# visit next row and column
self.print_diagonally(matrix, row + 1, col + 1, size)
end
# Recursively handles the request of printing diagonal elements
def print_element(matrix, i, size)
if (i >= size)
return
end
if (i == 0)
# First middle layer (First diagonal layer)
self.print_diagonally(matrix, i, 0, size)
else
# Bottom diagonal
self.print_diagonally(matrix, i, 0, size)
# Top diagonal
self.print_diagonally(matrix, 0, i, size)
end
self.print_element(matrix, i + 1, size)
end
end
def main()
obj = MyMatrix.new()
matrix = [
[1, 2, 3, 4, 5, 6] ,
[22, 23, 24, 25, 26, 7] ,
[21, 36, 37, 38, 27, 8] ,
[20, 35, 42, 39, 28, 9] ,
[19, 34, 41, 40, 29, 10] ,
[18, 33, 32, 31, 30, 11]
]
size = matrix.length
obj.print_element(matrix, 0, size)
end
main()
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
/*
Scala Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
// Print diagonally element
def print_diagonally(matrix: Array[Array[Int]], row: Int, col: Int, size: Int): Unit = {
if (row >= size || col >= size)
{
print("\n");
return;
}
print(" " + matrix(row)(col));
// visit next row and column
this.print_diagonally(matrix, row + 1, col + 1, size);
}
// Recursively handles the request of printing diagonal elements
def print_element(matrix: Array[Array[Int]], i: Int, size: Int): Unit = {
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
this.print_diagonally(matrix, i, 0, size);
}
else
{
// Bottom diagonal
this.print_diagonally(matrix, i, 0, size);
// Top diagonal
this.print_diagonally(matrix, 0, i, size);
}
this.print_element(matrix, i + 1, size);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
var matrix: Array[Array[Int]] = Array(
Array(1, 2, 3, 4, 5, 6),
Array(22, 23, 24, 25, 26, 7),
Array(21, 36, 37, 38, 27, 8),
Array(20, 35, 42, 39, 28, 9),
Array(19, 34, 41, 40, 29, 10),
Array(18, 33, 32, 31, 30, 11)
);
var size: Int = matrix.length;
obj.print_element(matrix, 0, size);
}
}
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
/*
Swift 4 Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
// Print diagonally element
func print_diagonally(_ matrix: [
[Int]
], _ row: Int, _ col: Int, _ size: Int)
{
if (row >= size || col >= size)
{
print("\n", terminator: "");
return;
}
print(" ", matrix[row][col], terminator: "");
// visit next row and column
self.print_diagonally(matrix, row + 1, col + 1, size);
}
// Recursively handles the request of printing diagonal elements
func print_element(_ matrix: [
[Int]
], _ i: Int, _ size: Int)
{
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
self.print_diagonally(matrix, i, 0, size);
}
else
{
// Bottom diagonal
self.print_diagonally(matrix, i, 0, size);
// Top diagonal
self.print_diagonally(matrix, 0, i, size);
}
self.print_element(matrix, i + 1, size);
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
let matrix: [
[Int]
] = [
[1, 2, 3, 4, 5, 6],
[22, 23, 24, 25, 26, 7],
[21, 36, 37, 38, 27, 8],
[20, 35, 42, 39, 28, 9],
[19, 34, 41, 40, 29, 10],
[18, 33, 32, 31, 30, 11]
];
let size: Int = matrix.count;
obj.print_element(matrix, 0, size);
}
main();
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
/*
Kotlin Program
Display Diagonally Bottom-Up matrix using Recursion
*/
class MyMatrix
{
// Print diagonally element
fun print_diagonally(matrix: Array<Array<Int>> , row: Int, col: Int, size: Int): Unit
{
if (row >= size || col >= size)
{
print("\n");
return;
}
print(" " + matrix[row][col]);
// visit next row and column
this.print_diagonally(matrix, row + 1, col + 1, size);
}
// Recursively handles the request of printing diagonal elements
fun print_element(matrix: Array<Array<Int>> , i: Int, size: Int): Unit
{
if (i >= size)
{
return;
}
if (i == 0)
{
// First middle layer (First diagonal layer)
this.print_diagonally(matrix, i, 0, size);
}
else
{
// Bottom diagonal
this.print_diagonally(matrix, i, 0, size);
// Top diagonal
this.print_diagonally(matrix, 0, i, size);
}
this.print_element(matrix, i + 1, size);
}
}
fun main(args: Array < String > ): Unit
{
var obj: MyMatrix = MyMatrix();
var matrix: Array<Array<Int>> = arrayOf(
arrayOf(1, 2, 3, 4, 5, 6),
arrayOf(22, 23, 24, 25, 26, 7),
arrayOf(21, 36, 37, 38, 27, 8),
arrayOf(20, 35, 42, 39, 28, 9),
arrayOf(19, 34, 41, 40, 29, 10),
arrayOf(18, 33, 32, 31, 30, 11)
);
var size: Int = matrix.count();
obj.print_element(matrix, 0, size);
}
Output
1 23 37 39 29 11
22 36 42 40 30
2 24 38 28 10
21 35 41 31
3 25 27 9
20 34 32
4 26 8
19 33
5 7
18
6
Resultant Output Explanation
The output consists of the elements of the input matrix printed diagonally from the bottom-left to the top-right. Each diagonal layer is printed on a new line, and the elements are separated by spaces.
Time Complexity
The time complexity of the given code is O(N^2) because for a square matrix of size N x N, we are visiting each element exactly once. The recursion is called N times, and at each recursion level, we print one element. Therefore, the overall time complexity is O(N^2).
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