c - 下面的代码生成 32x32 hadamard 矩阵。但是我如何递归地编写它呢？

Question

此代码将扩频因子作为输入，并将输出作为哈达玛矩阵。例如，如果扩频因子为 4，则哈达玛矩阵将为 4x4。谁能告诉我如何递归地编写它。

#include<stdio.h>

int main()
{
    int m = 2, i, j, spread_fact;
    int a[128][128], b[128][128];

    printf("enter the initial matrix\n");
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    printf("the entered matrix is\n");
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            printf("%d\t", a[i][j]);
        }
        printf("\n");
    }
    printf("enter the spreading factor\n");
    scanf("%d", &spread_fact);
    while (m < spread_fact) {
        m = 2 * m;
        printf("m value is:%d\n", m);
        for (i = 0; i < m / 2; i++) {
            for (j = 0; j < m / 2; j++) {
                b[i][j] = a[i][j];
            }
        }
        for (i = 0; i < m / 2; i++) {
            for (j = m / 2; j < m; j++) {
                b[i][j] = a[i][j - m / 2];
            }
        }
        for (i = m / 2; i < m; i++) {
            for (j = 0; j < m / 2; j++) {
                b[i][j] = a[i - m / 2][j];
            }
        }
        for (i = m / 2; i < m; i++) {
            for (j = m / 2; j < m; j++) {
                b[i][j] = -a[i - m / 2][j - m / 2];
            }
        }
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                a[i][j] = b[i][j];
                printf("the matrix is %d\n", a[i][j]);
            }
            printf("\n");
        }
        printf("the matrix is:\n");
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                printf("%d\t", a[i][j]);
            }
            printf("\n");
        }
    }

    return 0;
}

Answer 1

首先，让我们简化您的算法并将其包装到一个函数中:

void mhadam(int a[MAX][MAX], int m, int M)
{
    int i, j;

    while (m < M) {
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                a[i + m][j] = a[i][j];
                a[i][j + m] = a[i][j];
                a[i + m][j + m] = -a[i][j];
            }
        }
        m = 2 * m;
    }
}

这里的主要功能是 while 循环。如果尚未达到扩展因子 M，您可以递归调用此函数，而不是多次遍历此循环:

void mhadam_rec(int a[MAX][MAX], int m, int M)
{
    int i, j;

    if (m < M) {
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                a[i + m][j] = a[i][j];
                a[i][j + m] = a[i][j];
                a[i + m][j + m] = -a[i][j];
            }
        }
        mhadam_rec(a, 2*m, M);
    }
}

这里，循环和递归函数非常相似。在我看来，递归方法在这里不会给你带来任何好处。事实上，这种递归调用是函数中最后一条语句的递归称为尾递归，它们的特性之一是它们可以优化为循环。

编辑:为了完整起见，这里有一个计算 16×16 Hadamard 矩阵的小程序:

#include <stdio.h>

#define MAX 128

void mprint(int a[MAX][MAX], int m)
{
    int i, j;

    for (i = 0; i < m; i++) {
        for (j = 0; j < m; j++) {
            printf("%4d", a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void mhadam_rec(int a[MAX][MAX], int m, int M)
{
    int i, j;

    if (m < M) {
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                a[i + m][j] = a[i][j];
                a[i][j + m] = a[i][j];
                a[i + m][j + m] = -a[i][j];
            }
        }
        mhadam_rec(a, 2*m, M);
    }
}

int main()
{
    int a[MAX][MAX];
    int m = 1;
    int M = 16;

    a[0][0] = 1;

    mhadam_rec(a, m, M);
    mprint(a, M);

    return 0;
}