C语言递归验证对称矩阵的异常问题与实现方案咨询

异常输出原因说明 #

你遇到的连续两次运行后打印大量输入提示的问题和递归函数无关，属于输入缓冲区残留导致的问题：
第一次运行时你未输入矩阵阶数就结束进程，scanf("%d", &n)没有读取到有效输入，非法值残留在输入缓冲区中，第二次运行时scanf直接读取该残留值给n，导致n变成远大于20的非法值，输入循环因此执行了远超预期的次数，打印大量提示。只需要在读取n后增加合法性校验即可解决：

if (n < 1 || n > 20) {
    printf("矩阵阶数只能是1~20之间的整数");
    return 1;
}

另外你代码中生成转置矩阵t的逻辑完全没有被使用，属于冗余代码，可以直接删除。

现有递归函数的问题 #

你写的递归函数逻辑上可以得到正确结果，但存在两个明显缺陷：

1. 指数级时间复杂度：你使用双分支递归同时往下走i+1和j+1两个路径，会导致同一对下标(i,j)被多次重复校验，比如(1,1)会被(0,1)的分支和(1,0)的分支各校验一次，n越大重复校验的次数增长越快，n=20时会产生数万次无意义的递归调用，效率极低。
2. 冗余校验：对称矩阵只需要校验上三角（或下三角）的非对角线元素即可，对角线元素m[i][i]本身必然等于自己，不需要校验；(i,j)和(j,i)也只需要校验一次即可，你当前的逻辑会把所有下标组合全部校验一遍，做了很多无用功。

你有疑问的那行代码return (verifySymmetric(m, i + 1, j, n) && verifySymmetric(m, i, j + 1, n));本身的逻辑是对的（要求两个分支的校验都通过才返回真），但就是这个双分支逻辑导致了大量重复递归调用。

其他递归实现思路 #

这里给出两种更高效的递归实现，时间复杂度和循环版本一致为O(n²)，没有冗余调用：

思路1：按行递归+行内循环校验 #

每次递归处理一行，只校验当前行中列下标大于行下标的元素（即上三角元素），全部校验通过后递归处理下一行，直到所有行处理完成返回真。

int verifySymmetric(int m[20][20], int cur_row, int n) {
    // 所有行处理完成，矩阵对称
    if (cur_row >= n - 1) {
        return 1;
    }
    // 校验当前行的所有上三角元素
    for (int cur_col = cur_row + 1; cur_col < n; cur_col++) {
        if (m[cur_row][cur_col] != m[cur_col][cur_row]) {
            return 0;
        }
    }
    // 递归处理下一行
    return verifySymmetric(m, cur_row + 1, n);
}

调用方式：verifySymmetric(m, 0, n)

思路2：纯递归逐元素校验 #

完全不使用循环，仅用递归逐元素遍历上三角区域，每次到行尾就跳转到下一行的上三角起始位置继续校验：

int verifySymmetric(int m[20][20], int cur_row, int cur_col, int n) {
    // 所有行处理完成，矩阵对称
    if (cur_row >= n - 1) {
        return 1;
    }
    // 当前行处理完成，跳转到下一行的上三角起始位置
    if (cur_col >= n) {
        return verifySymmetric(m, cur_row + 1, cur_row + 2, n);
    }
    // 元素不相等，直接返回假
    if (m[cur_row][cur_col] != m[cur_col][cur_row]) {
        return 0;
    }
    // 递归校验当前行的下一个元素
    return verifySymmetric(m, cur_row, cur_col + 1, n);
}

调用方式：verifySymmetric(m, 0, 1, n)

内容的提问来源于stack exchange，提问作者欲しい未来