complex<double>* fft(double *f, int N)
{
    vector<complex<double>> y;


    if (N == 1)
    {
        y[0] = f[0];
        return &y[0];
    }


    complex<double>* y0 = new complex<double>[N/2];
    complex<double>* y1 = new complex<double>[N/2];

    double* f1 =new double(N / 2);
    double* f2= new double(N / 2);


    for (int i = 0; i < N / 2; i++)
    {
        f1[i] = f[i * 2];
        f2[i] = f[i * 2 + 1];
    }

    y0 = fft(f1,N);
    y1 = fft(f2,N);

    vector<complex<double>> w;
    for (int i = 0; i < N; i++) {
        double alpha = 2 * pi * i / N;
        w[i] = (cos(alpha), sin(alpha));
    }


    for (int k = 0; k < N / 2; k++) {
        y[k] = y0[k] + w[k] * y1[k];
        y.push_back(y[k]);
        y[k + N / 2] = y0[k] - w[k] * y1[k];
        y.push_back(y[k+N/2]);
    }
    return y;
}