Posted on by Kalkicode
Code Recursion

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

1. We have two main functions, `print_diagonally` and `print_element`, to handle the recursion for printing diagonal elements.
2. The `print_diagonally` function prints the diagonal elements starting from a given position `(row, col)`.
3. The `print_element` function handles the recursive requests for printing diagonal elements for each diagonal layer.
4. The `print_element` function starts with `i=0`, which means it prints the first middle layer (the main diagonal) using the `print_diagonally` function.
5. For each subsequent diagonal layer, the `print_element` function calls `print_diagonally` twice: once for the bottom diagonal and once for the top diagonal, by adjusting the starting positions accordingly.
6. The recursion continues until all diagonal layers are printed.
7. In the main function, we initialize the matrix and call `print_element` with `i=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).

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