fast fourier transform with recursion

fft.c

void _fft(double* buf, double* out, unsigned int n, unsigned int step){
    if(step<n){
        _fft(out, buf, n, step*2);
        _fft(out+step, buf+step, n, step*2);
        int i;
        for(i=0;i<n;i += 2*step){
            double t = cexp(-I*PI*i/n)*out[i+step];
            buf[i/2] = out[i] + t;
            buf[(i+n)/2] = out[i] - t;
        }
    }
}

void fft(double* buf, unsigned int n){
    double* out = (double*)malloc(sizeof(double)*n);
    int i;
    for(i=0;i<n;i++) out[i] = buf[i];
    _fft(buf, out, n, 1);
}