CC-12 : Implement matrix multiplication using recursion.
Description:
Given two input matrices, find and return their product.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
The 1st matrix :
1,2,3,
4,6,7,
5,8,0,
The 2nd matrix :
1,5,4,
2,6,0,
3,8,7,
|
The multiplied matrix :
14,41,25,
37,112,65,
21,73,20,
|
Pseudocode:
| Initialize variables row3,col3, .k to 0 at class level.
|
matrixMultiplication (row1, col1,matrix1,row2,col2,matrix2, matrix3):
| If row3>=row1 then return ; (base case).
|
If row3 < row1:
If col3
If k
Matrix3[row][col]+=matrx1[row3][k]*matrix2[k][cols3].
Increment k by 1.
Recursively call matrixMultiplication (row1, col1,matrix1,row2,col2,matrix2, matrix3).
Set k to 0.
Increment col3 by 1.
Recursively call matrixMultiplication (row1, col1,matrix1,row2,col2,matrix2, matrix3).
Set col3 to 0.
Increment row3++.
Recursively call matrixMultiplication (row1, col1,matrix1,row2,col2,matrix2, matrix3).
|
| Return.
|
Code:
public class RecursionMatrixMultiplication {
private int row3 = 0; int col3 = 0; int k = 0;
public void matrixMultiplication(int row1, int col1, int[][] matrix1, int row2,
int col2, int[][] matrix2, int[][] matrix3) {
if (row3 >= row1) { return;}
if (row3 < row1) {
if (col3 < col2) {
if (k < col1) {
matrix3[row3][col3] += matrix1[row3][k] * matrix2[k][col3];
k++;
matrixMultiplication(row1, col1, matrix1, row2, col2, matrix2, matrix3);
}
k = 0;
col3++;
matrixMultiplication(row1, col1, matrix1, row2, col2, matrix2, matrix3);
}
col3 = 0;
row3++;
matrixMultiplication(row1, col1, matrix1, row2, col2, matrix2, matrix3);
}
}
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class RecursionMatrixMultiplication {
private int row3 = 0; int col3 = 0; int k = 0;
public void matrixMultiplication(int row1, int col1, int[][] matrix1, int row2,
int col2, int[][] matrix2, int[][] matrix3) {
if (row3 >= row1) { return;}
if (row3 < row1) {
if (col3 < col2) {
if (k < col1) {
matrix3[row3][col3] += matrix1[row3][k] * matrix2[k][col3];
k++;
matrixMultiplication(row1, col1, matrix1, row2, col2, matrix2, matrix3);
}
k = 0;
col3++;
matrixMultiplication(row1, col1, matrix1, row2, col2, matrix2, matrix3);
}
col3 = 0;
row3++;
matrixMultiplication(row1, col1, matrix1, row2, col2, matrix2, matrix3);
}
}
public static void print2dArray(int[][] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("***********************************************************************");
System.out.print(label+" : \n");
int rIdx=0; int cIdx=0;
for (rIdx=0; rIdx < intArray.length; rIdx++) {
for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
System.out.print(intArray[rIdx][cIdx]);
if (cIdx < intArray[rIdx].length) System.out.print(",");
}
System.out.print("\n");
}
System.out.println();
System.out.println("************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
/************************
Test cases given below:
***********************/
RecursionMatrixMultiplication ap=new RecursionMatrixMultiplication();
int[][] retArr;
try {
int[][] arr1 = {{1,2,3},
{4,6,7},
{5,8,0}
};
int[][] arr2 = { {1,5,4},
{2,6,0},
{3,8,7}
};
int[][] arr3=new int[3][3];
print2dArray(arr1, "The 1st matrix");
print2dArray(arr2, "The 2nd matrix");
ap.matrixMultiplication(3,3,arr1,3,3,arr2,arr3);
print2dArray(arr3, "The mutiplied matrix");
}catch (Exception exception) {
System.out.print("Exception,"+ exception);
exception.printStackTrace();
}
}
}