Example: Recursive Matrix Multiplication in C++

// 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;
}