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.

New Comment





Categories
Relative Post