FFT

ComplexData * FFTrecursion(ComplexData * data, int N) {
    if (N == 1) {
        return data;
    } else {
        int No2 = N/2;
        float pi2oN = 6.28318/(N*1.0f);
        ComplexData * output = new ComplexData[N];
        ComplexData * splitdata = new ComplexData[No2];

        for (int i = 0; i < No2; i++) {
            splitdata[i].r = data[i*2].r;
            splitdata[i].i = data[i*2].i;
        }
        ComplexData * even = FFTrecursion(splitdata,No2);

        for (int i = 0; i < No2; i++) {
            splitdata[i].r = data[i*2+1].r;
            splitdata[i].i = data[i*2+1].i;
        }
        ComplexData * odd = FFTrecursion(splitdata,No2);

        for (int k = 0; k < No2; k++) {
            float A = pi2oN*k;
            float cosA = cos(A);
            float sinA = sin(A);
            float oddk_r = odd[k].r*cosA + odd[k].i*sinA;
            float oddk_i = odd[k].r*sinA - odd[k].i*cosA;
            output[k].r = even[k].r + oddk_r;
            output[k].i = even[k].i + oddk_i;
            output[k+No2].r = even[k].r - oddk_r;
            output[k+No2].i = even[k].i - oddk_i;
        }
        delete [] splitdata;
        return output;
    }
}