C++ Program To Perform Matrix Multiplication Using Recursion

Matrix multiplication is a fundamental operation in linear algebra, widely used across various scientific and engineering disciplines. While typically implemented using nested loops, exploring recursive solutions offers a different perspective on problem-solving and can highlight the power of divide-and-conquer strategies. In this article, you will learn how to implement matrix multiplication using a recursive approach in C++.

Problem Statement

Matrix multiplication involves multiplying two matrices, say matrix A (of dimension m x n) and matrix B (of dimension n x p), to produce a resultant matrix C (of dimension m x p). For this operation to be valid, the number of columns in the first matrix must equal the number of rows in the second matrix. Each element C[i][j] in the resultant matrix is computed as the sum of products of corresponding elements from the i-th row of A and the j-th column of B. Mathematically, C[i][j] = Σ (A[i][k] * B[k][j]) for k from 0 to n-1.

This problem becomes computationally intensive for large matrices, making efficient algorithms crucial. While recursive approaches often carry overhead, they can offer elegant solutions or lead to more optimized algorithms like Strassen's algorithm.

Example

Consider two 2x2 matrices:

Matrix A:

1 2
3 4

Matrix B:

5 6
7 8

The product matrix C would be:

C[0][0] = (1*5) + (2*7) = 5 + 14 = 19
C[0][1] = (1*6) + (2*8) = 6 + 16 = 22
C[1][0] = (3*5) + (4*7) = 15 + 28 = 43
C[1][1] = (3*6) + (4*8) = 18 + 32 = 50

Resultant Matrix C:

19 22
43 50

Background & Knowledge Prerequisites

To understand and implement recursive matrix multiplication in C++, you should be familiar with:

• C++ Basics: Fundamental syntax, data types, variables, and control flow statements.
• Functions: Defining and calling functions, understanding parameters and return types.
• Arrays (2D Arrays): Declaring, initializing, and accessing elements in two-dimensional arrays, which are used to represent matrices.
• Recursion: The concept of a function calling itself, including base cases and recursive steps.
• Pointers (Optional but good for dynamic memory): While not strictly required for fixed-size matrices, dynamic allocation with pointers is common for general matrix operations. For simplicity, we will use fixed-size arrays in our example.

Use Cases or Case Studies

Matrix multiplication is a cornerstone in many fields:

• Computer Graphics: Used extensively for transformations like scaling, rotation, and translation of 3D objects in games and simulations.
• Machine Learning and Deep Learning: Core operation in neural networks for forward and backward propagation, especially in layers like fully connected layers and convolutions.
• Image Processing: Applied in filters, transformations, and compression algorithms for images.
• Physics and Engineering Simulations: Solving systems of linear equations, finite element analysis, and quantum mechanics calculations.
• Data Science and Statistics: Covariance matrices, principal component analysis (PCA), and various statistical models rely heavily on matrix operations.

Solution Approaches

Recursive Calculation of Matrix Elements

This approach focuses on making the summation part of computing each C[i][j] element recursive. Instead of using a loop for k to sum products A[i][k] * B[k][j], we define a recursive function that performs this summation. The outer loops (for i and j) still iterate, but the core element calculation is handled recursively.

One-line summary: Calculate each element C[i][j] by recursively summing the products of corresponding elements from A[i][k] and B[k][j].

Code Example:

// Recursive Matrix Multiplication
#include <iostream>
#include <vector> // Using std::vector for dynamic size matrices

// Function to recursively calculate a single element C[row][col]
// 'k' is the current index for summation (from 0 to N-1)
// 'N' is the common dimension (columns of A / rows of B)
int calculateElementRecursively(const std::vector<std::vector<int>>& A,
                                 const std::vector<std::vector<int>>& B,
                                 int row, int col, int k, int N) {
    // Base case: If 'k' reaches N, the summation for this element is complete.
    if (k == N) {
        return 0;
    }
    // Recursive step: Add A[row][k] * B[k][col] to the sum of subsequent terms.
    return (A[row][k] * B[k][col]) + calculateElementRecursively(A, B, row, col, k + 1, N);
}

// Function to perform matrix multiplication using the recursive element calculation
void multiplyMatrices(const std::vector<std::vector<int>>& A,
                      const std::vector<std::vector<int>>& B,
                      std::vector<std::vector<int>>& C,
                      int M, int N, int P) {
    // M: rows of A, N: columns of A (and rows of B), P: columns of B

    // Iterate through each row of matrix A
    for (int i = 0; i < M; ++i) {
        // Iterate through each column of matrix B
        for (int j = 0; j < P; ++j) {
            // Calculate C[i][j] recursively
            C[i][j] = calculateElementRecursively(A, B, i, j, 0, N);
        }
    }
}

// Function to print a matrix
void printMatrix(const std::vector<std::vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    // Define matrices A and B
    std::vector<std::vector<int>> A = {{1, 2}, {3, 4}}; // 2x2 matrix
    std::vector<std::vector<int>> B = {{5, 6}, {7, 8}}; // 2x2 matrix

    int M = A.size();       // Number of rows in A
    int N = A[0].size();    // Number of columns in A (and rows in B)
    int P = B[0].size();    // Number of columns in B

    // Check if multiplication is possible
    if (N != B.size()) {
        std::cout << "Error: Matrix dimensions are not compatible for multiplication." << std::endl;
        return 1;
    }

    // Initialize result matrix C with dimensions M x P
    std::vector<std::vector<int>> C(M, std::vector<int>(P));

    std::cout << "Matrix A:" << std::endl;
    printMatrix(A);
    std::cout << "\\nMatrix B:" << std::endl;
    printMatrix(B);

    // Perform matrix multiplication
    multiplyMatrices(A, B, C, M, N, P);

    std::cout << "\\nResultant Matrix C (A * B):" << std::endl;
    printMatrix(C);

    return 0;
}

Run

Sample Output:

Matrix A:
1 2 
3 4 

Matrix B:
5 6 
7 8 

Resultant Matrix C (A * B):
19 22 
43 50

Stepwise Explanation:

1. calculateElementRecursively(A, B, row, col, k, N) function:

• This is the core recursive function responsible for computing a single element C[row][col].
• A and B are the input matrices. row and col specify the current element in matrix C being calculated.
• k is the index that varies from 0 to N-1. It represents the column index for matrix A and the row index for matrix B during the summation.
• N is the common dimension, i.e., the number of columns in A (which must equal the number of rows in B).
• Base Case: If k == N, it means we have iterated through all required terms for the summation. At this point, the sum is complete, so we return 0 (as there are no more terms to add).
• Recursive Step: Otherwise, we calculate the product of A[row][k] and B[k][col]. We then add this product to the result of a recursive call to calculateElementRecursively, where k is incremented by 1. This process continues until the base case is reached, accumulating the sum of all products.

1. multiplyMatrices(A, B, C, M, N, P) function:

• This function orchestrates the overall matrix multiplication.
• It takes three matrices (A, B, C) and their dimensions (M = rows of A, N = columns of A/rows of B, P = columns of B).
• It uses two nested for loops:
• The outer loop iterates from i = 0 to M-1 (for each row of matrix A).
• The inner loop iterates from j = 0 to P-1 (for each column of matrix B).
• Inside these loops, for each C[i][j] element, it calls calculateElementRecursively(A, B, i, j, 0, N). This initiates the recursive summation for that specific element, starting k from 0.

1. main() function:

• Initializes two example matrices A and B.
• Determines their dimensions (M, N, P).
• Performs a crucial check to ensure matrix dimensions are compatible for multiplication (N from A must equal rows of B).
• Initializes the result matrix C with the appropriate dimensions.
• Calls multiplyMatrices to perform the operation.
• Prints all matrices for verification.

Conclusion

Implementing matrix multiplication recursively, even for the inner element summation, showcases how complex operations can be broken down into simpler, self-similar steps. While this specific recursive approach for element calculation does not offer performance benefits over iterative methods due to function call overhead, it serves as a clear illustration of applying recursion to a fundamental algorithm. More advanced recursive matrix multiplication algorithms, like Strassen's algorithm, demonstrate significant complexity advantages for very large matrices by performing a true divide-and-conquer on the matrices themselves.

Summary

• Matrix multiplication C = A * B requires the number of columns in A to equal the number of rows in B.
• Each element C[i][j] is the sum of products A[i][k] * B[k][j] for k from 0 to N-1.
• A recursive approach can be used to calculate this summation for each C[i][j] element.
• The recursive function calculateElementRecursively has a base case (when k reaches N) and a recursive step that adds the current product A[row][k] * B[k][col] to the sum of subsequent terms.
• While conceptually elegant, simple recursive element calculation might incur performance overhead compared to iterative loops due to function call stack management.