Recursive function to verify Matrix is Symmetric in C

user_14857866 0
Viewed 114

I am just working on a recursive function to verify if a matrix is symmetric or not. The matrix must be square and I am considering max n = 20. I could develop the function:

int verifySymmetric(int m[20][20], int i, int j, int n) {
    if (!((n == i) || (n == j))) {
        if (m[i][j] != m[j][i]) {
            return 0;
        } else {
            return (verifySymmetric(m, i + 1, j, n) && verifySymmetric(m, i, j + 1, n));
        }
    }
    return 1;   
}

Below is a code to run:

#include <stdio.h>
#include <stdlib.h>

int verifySymmetric(int m[20][20], int i, int j, int n) {
    if (!((n == i) || (n == j))) {
       if (m[i][j] != m[j][i]) {
            return 0;
        } else {
            return (verifySymmetric(m, i + 1, j, n) && verifySymmetric(m, i, j + 1, n));
        }
    }
    return 1;   
}
    
int main() {
    int n, r, c, m[20][20], t[20][20], flag, i, j;
    i = j = 0;

    printf("Enter matrix order >> ");
    scanf("%d", &n);

    printf("\nEnter the elements \n");

    for (r = 0; r < n; r++) {
        for (c = 0; c < n; c++) {
            printf("m[%d][%d]: ", r + 1, c + 1);
            scanf("%d", &m[r][c]);
        }
    }

    for (r = 0; r < n; r++)                  
        for (c = 0; c < n; c++)          
            t[c][r] = m[r][c]; 

    flag = verifySymmetric(m, i, j, n);

    if (flag == 1)
        printf("Matrix is symmetric ");
    if (flag == 0)
        printf("Matrix is not symmetric ");

    return 0;
}

My main concern is about the line

return (verifySymmetric(m, i + 1, j, n) && verifySymmetric(m, i, j + 1, n));

The program seem to work but I noticed that many m[row][column] is printed when I run the code. Something like this

Enter the elements
m[1][1]: m[1][2]: m[1][3]: m[1][4]: m[1][5]: m[1][6]: m[1][7]: m[1][8]: m[1][9]: m[1][10]: m[1] 
[11]: m[1][12]: m[1][13]: m[1][14]: m[1][15]: m[1][16]: m[1][17]: m[1][18]: m[1][19]: m[1][20]: 
m[1][21]: m[1][22]: m[1][23]: m[1][24]: m[1][25]: m[1][26]: m[1][27]: m[1][28]: m[1][29]: m[1] 
[30]: m[1][31]: m[1][32]: m[1][33]: m[1][34]: m[1][35]: m[1][36]: m[1][37]: m[1][38]: m[1][39]: 
 m[1][40]: m[1][41]: m[1][42]: m[1][43]: m[1][44]: m[2][1]: m[2][2]: m[2][3]: m[2][4]: m[2][5]: 
 m[2][6]: m[2][7]: m[2][8]: m[2][9]: m[2][10]: m[2][11]: m[2][12]: m[2][13]: m[2][14]: m[2][15]: 
 m[2][16]: m[2][17]: m[2][18]: m[2][19]: m[2][20]: m[2][21]: m[2][22]: m[2][23]: m[2][24]:

What would be wrong with the function?

What would be another approach?

Edit

This is not a good approach, using recursion for a function like this, but I was curious about it and couldn't find an example in the internet. It is basically for learning purposes.

I am using Visual Studio Code and the strange behavior described above is when I click to Run Code two times. Running once, it runs as I expected, printing Enter matrix order >> , but once I click it for the second time without entering the matrix order, the misbehavior happens.

recursion matrix c
1 Answers

The code seems to work but it is very inefficient as the recursive approach will cause many redundant comparisons. The time complexity is O(n4) instead of O(n2)

You reason you get this misleading output is you prompt for each matrix value to stdout, but the input is read from a file and not echoed to stdout.

Here is a simpler non-recursive approach:

#include <stdio.h>

int verifySymmetric(int m[20][20], int n) {
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < r; c++) {
            if (m[r][c] != m[c][r])
                return 0;
        }
    }
    return 1;
}
    
int main() {
    int n, m[20][20];

    printf("Enter matrix order >> ");
    if (scanf("%d", &n) != 1) {
        printf("missing input\n");
        return 1;
    }
    if (n < 1 || n > 20) {
        printf("invalid dimension %d\n", n);
        return 1;
    }

    printf("\nEnter the elements\n");

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++)
            if (scanf("%d", &m[r][c]) != 1) {
                printf("missing input\n");
                return 1;
            }
        }
    }

    if (verifySymmetric(m, n)) {
        printf("Matrix is symmetric\n");
    else
        printf("Matrix is not symmetric\n");

    return 0;
}

If for some reason the implementation is required to be recursive, here is a modified version without redundant comparisons:

int verifySymmetric(int m[20][20], int i, int j, int n) {
    if (j == n) {
        return 1;
    } else
    if (i < j) {
        return (m[i][j] == m[j][i]) && verifySymmetric(m, i + 1, j, n);
    } else {
        return verifySymmetric(m, 0, j + 1, n);
    }
}
user_45932670
Related