数字信号处理C语言FFT

以下是一个数字信号处理的C语言FFT的例子：

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

#define PI 3.14159265358979323846

void fft(double complex *x, int n) {
    if (n <= 1) {
        return;
    }
    double complex *even = malloc(n / 2 * sizeof(double complex));
    double complex *odd = malloc(n / 2 * sizeof(double complex));
    for (int i = 0; i < n / 2; i++) {
        even[i] = x[2 * i];
        odd[i] = x[2 * i + 1];
    }
    fft(even, n / 2);
    fft(odd, n / 2);
    for (int i = 0; i < n / 2; i++) {
        double complex t = cexp(-I * PI * i / n) * odd[i];
        x[i] = even[i] + t;
        x[i + n / 2] = even[i] - t;
    }
    free(even);
    free(odd);
}

int main() {
    double complex x[] = {1, 2, 3, 4};
    int n = sizeof(x) / sizeof(x[0]);
    fft(x, n);
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", creal(x[i]), cimag(x[i]));
    }
    return 0;
}