C Program To Perform Matrix Multiplication Using Recursion

Matrix multiplication is a fundamental operation in linear algebra with wide-ranging applications. While often implemented iteratively, understanding its recursive formulation can offer deeper insights into algorithmic design, particularly divide-and-conquer strategies. In this article, you will learn how to perform matrix multiplication using a recursive approach in C, breaking down the problem into smaller, manageable sub-problems.

Problem Statement

Multiplying two matrices, A (of size $M \times N$) and B (of size $N \times P$), results in a matrix C (of size $M \times P$). Each element $C_{ij}$ of the result matrix is computed as the sum of the products of elements from the $i$-th row of A and the $j$-th column of B. Mathematically, $C_{ij} = \sum_{k=0}^{N-1} A_{ik} \times B_{kj}$. The challenge lies in efficiently performing this summation for all elements, and specifically, doing so recursively rather than with traditional nested loops.

Example

Consider two $2 \times 2$ matrices:

Matrix A:

1 2
3 4

Matrix B:

5 6
7 8

The product C = A * B would be:

(1*5 + 2*7)  (1*6 + 2*8)
(3*5 + 4*7)  (3*6 + 4*8)

Result Matrix C:

19 22
43 50

Background & Knowledge Prerequisites

To understand recursive matrix multiplication, you should be familiar with:

• C Programming Basics: Variables, data types, arrays, functions, pointers.
• Functions: Defining and calling functions, passing arguments.
• Recursion: The concept of a function calling itself, base cases, and recursive steps.
• Multidimensional Arrays: How to declare and access elements in 2D arrays (matrices).
• Memory Allocation: Basic understanding of how arrays are stored.

For this specific implementation, no special libraries beyond stdio.h are required.

Use Cases or Case Studies

Matrix multiplication is a cornerstone in various fields:

• Computer Graphics: Used for transformations like rotation, scaling, and translation of objects in 2D and 3D space.
• Image Processing: Applied in filters, convolutions, and various transformations for image enhancement and analysis.
• Scientific Computing: Essential for solving systems of linear equations, simulations, and data analysis in fields like physics, engineering, and economics.
• Machine Learning: Forms the core of neural network operations, especially in forward and backpropagation for matrix-vector and matrix-matrix products.
• Cryptography: Utilized in certain encryption algorithms and codes.

Solution Approaches

While the most famous recursive matrix multiplication algorithm is Strassen's algorithm (a divide-and-conquer approach with better asymptotic complexity), for simplicity and clarity in demonstrating basic recursion, we will focus on a more direct recursive computation of each element of the product matrix.

Recursive Element Calculation

This approach focuses on calculating each element $C_{ij}$ of the result matrix using a recursive function. The function will compute the sum of products $A_{ik} \times B_{kj}$ by recursively iterating through the k dimension.

One-line summary: Compute each element of the result matrix using a recursive function to sum the products across the common dimension.

// Matrix Multiplication using Recursion
#include <stdio.h>

#define MAX_SIZE 10 // Maximum size for matrices

// Global matrices for simplicity, in a real app, pass them as arguments
int A[MAX_SIZE][MAX_SIZE];
int B[MAX_SIZE][MAX_SIZE];
int C[MAX_SIZE][MAX_SIZE];

// Recursive function to calculate a single element C[row][col]
// k: current index for summation (common dimension)
// dim_k: dimension N (number of columns in A / rows in B)
int calculateElementRecursive(int row, int col, int k, int dim_k) {
    // Base Case: If k reaches dim_k, the summation is complete for this element
    if (k == dim_k) {
        return 0;
    }
    // Recursive Step: Add the current product and recurse for the next k
    return (A[row][k] * B[k][col]) + calculateElementRecursive(row, col, k + 1, dim_k);
}

// Function to perform matrix multiplication using the recursive element calculation
void multiplyMatrices(int r1, int c1, int r2, int c2) {
    // Check if multiplication is possible
    if (c1 != r2) {
        printf("Error: Number of columns in the first matrix must equal number of rows in the second.\\n");
        return;
    }

    // Iterate through rows of result matrix C
    for (int i = 0; i < r1; i++) {
        // Iterate through columns of result matrix C
        for (int j = 0; j < c2; j++) {
            // Calculate C[i][j] using the recursive helper function
            C[i][j] = calculateElementRecursive(i, j, 0, c1); // c1 is the common dimension (N)
        }
    }
}

// Function to print a matrix
void printMatrix(int rows, int cols, int matrix[MAX_SIZE][MAX_SIZE]) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%4d ", matrix[i][j]);
        }
        printf("\\n");
    }
}

int main() {
    int r1, c1, r2, c2;

    // Define matrix dimensions
    r1 = 2; c1 = 2; // Matrix A: 2x2
    r2 = 2; c2 = 2; // Matrix B: 2x2

    // Initialize Matrix A
    A[0][0] = 1; A[0][1] = 2;
    A[1][0] = 3; A[1][1] = 4;

    // Initialize Matrix B
    B[0][0] = 5; B[0][1] = 6;
    B[1][0] = 7; B[1][1] = 8;

    printf("Matrix A:\\n");
    printMatrix(r1, c1, A);
    printf("\\nMatrix B:\\n");
    printMatrix(r2, c2, B);

    // Perform matrix multiplication
    multiplyMatrices(r1, c1, r2, c2);

    printf("\\nResult Matrix C (A * B) using recursion:\\n");
    printMatrix(r1, c2, C);

    // Another example: 3x2 * 2x3
    r1 = 3; c1 = 2; // Matrix A: 3x2
    r2 = 2; c2 = 3; // Matrix B: 2x3

    // Re-initialize Matrix A
    A[0][0] = 1; A[0][1] = 2;
    A[1][0] = 3; A[1][1] = 4;
    A[2][0] = 5; A[2][1] = 6;

    // Re-initialize Matrix B
    B[0][0] = 7; B[0][1] = 8; B[0][2] = 9;
    B[1][0] = 0; B[1][1] = 1; B[1][2] = 2;

    printf("\\n--- Second Example ---\\n");
    printf("Matrix A (3x2):\\n");
    printMatrix(r1, c1, A);
    printf("\\nMatrix B (2x3):\\n");
    printMatrix(r2, c2, B);

    // Perform matrix multiplication
    multiplyMatrices(r1, c1, r2, c2);

    printf("\\nResult Matrix C (A * B) using recursion:\\n");
    printMatrix(r1, c2, C); // Result will be 3x3

    return 0;
}

Run

Sample Output:

Matrix A:
   1    2 
   3    4 

Matrix B:
   5    6 
   7    8 

Result Matrix C (A * B) using recursion:
  19   22 
  43   50 

--- Second Example ---
Matrix A (3x2):
   1    2 
   3    4 
   5    6 

Matrix B (2x3):
   7    8    9 
   0    1    2 

Result Matrix C (A * B) using recursion:
   7   10   13 
  21   28   35 
  35   46   57

Stepwise Explanation:

1. Global Matrices: For simplicity in this example, matrices A, B, and C are declared globally. In production code, it's better to pass them as function arguments.
2. calculateElementRecursive(row, col, k, dim_k) Function:
   • This is the core recursive function. It's responsible for calculating the value of a single element C[row][col].

row and col are the fixed indices of the element in the result matrix C that we are currently computing.

k is the index that iterates through the common dimension (number of columns in A / rows in B). It starts at 0 and goes up to dim_k - 1.

Base Case: If k equals dim_k, it means we have iterated through all necessary products for the sum. At this point, the sum for C[row][col] is complete, so the function returns 0.

Recursive Step: It calculates A[row][k] * B[k][col] (the current product) and adds it to the result of calling itself with k + 1. This continues until the base case is reached, accumulating the sum.

1. multiplyMatrices(r1, c1, r2, c2) Function:
   • This function orchestrates the matrix multiplication. It checks for valid dimensions (c1 == r2).

It uses nested for loops to iterate through each row (i) of the first matrix and each col (j) of the second matrix.

For each pair (i, j), it calls calculateElementRecursive(i, j, 0, c1) to compute the corresponding element C[i][j]. The 0 indicates starting the k iteration from the first element, and c1 (columns of A / rows of B) is the common dimension for k.

1. printMatrix and main Functions:
   • printMatrix is a utility function to display the matrix contents.

main initializes two matrices A and B, prints them, calls multiplyMatrices to perform the recursive multiplication, and then prints the resulting matrix C. Two examples are provided for clarity.

Conclusion

Implementing matrix multiplication recursively, even for the element-wise sum, demonstrates a fundamental application of recursion in C. While this specific recursive approach for calculating each element might not offer performance benefits over iterative methods due to function call overhead, it clearly illustrates how a complex summation can be broken down into simpler, self-similar problems. This understanding is foundational for more advanced recursive algorithms like Strassen's, which leverage divide-and-conquer for improved efficiency.

Summary

• Matrix multiplication C = A * B means C[i][j] is the sum of products A[i][k] * B[k][j].
• A recursive approach calculates each C[i][j] by defining a base case (end of summation) and a recursive step (current product + recursive sum).
• The calculateElementRecursive function sums A[row][k] * B[k][col] by incrementing k in subsequent calls until the base case is met.
• This method clearly illustrates recursion but may incur overhead compared to iterative loops for basic element calculation.
• Matrix multiplication is vital for computer graphics, scientific computing, image processing, and machine learning.