Example: Matrix Multiplication using Recursion in C

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