Thread: Having issues with my FFT

I coded up an FFT, and I'm having issues with it. I can't figure out what the problem is. It's not the 1st time I've coded the FFT, and I've compared my new FFT code (in C++) to a previous time I coded the FFT (in C#), and I don't personally see any mistakes in the way I've coded it (although the two implementations have some minor semantic differences).

Here is the graph of the signal I am sending into the function:

Attachment 9674

Here is the graph I should get as output:

Attachment 9672

And here is what I really am getting as output:

Attachment 9673

The output off the fft looks oddly like the sync function...which shouldn't be the result for a simple sine wave...

Here is my code:

Code:

std::vector < std::complex<double> > InternalFastFourierTransform (std::vector < std::complex<double> > input)
{
    static std::complex<double> i = std::complex<double>(0, 1);
    static std::complex<double> NegativeTwoPiI = -2.0 * PI * i;

    int N = (int)input.size();
    int halfN = N / 2;

    if (N == 1)
    {
        return input;
    }
    else
    {
        //Recurse and get evens/odds
        std::vector< std::complex<double> > evens = InternalFastFourierTransform( GetVectorRange(input, 0, N, 2) );
        std::vector< std::complex<double> > odds = InternalFastFourierTransform( GetVectorRange(input, 1, N, 2) );

        //Combine
        std::vector< std::complex<double> > result = std::vector< std::complex<double> > (N);
        for(int k = 0; k < halfN; k++)
        {
            std::complex<double> exponent = std::exp(NegativeTwoPiI * double(k / N));
            result[k] = evens[k] + exponent * odds[k];
            result[k + halfN] = evens[k] - exponent * odds[k];
        }

        return result;
    }
}

Do you guys see anything wrong? The only thing that I could see is that possibly my function GetVectorRange which takes a slice of a vector from some starting index to some ending index at a stride of 2 could be functiong incorrectly...I haven't thoroughly tested that function...but is that really the problem, or do you think it could be some math mistake based off of the graph output?