Most of tonight I was looking at different ways I could approach the Fast Fourier Transform (FFT) so that I could convert a sampled audio signal into a usable frequency spectrum. I've looked at tons of pseudocode and other implementations but this seems to be the most simple method. If you have time and know what I'm talking about, please take a look and see if you can find out whats wrong. Thanks!

This is the recursive C reference.

/*{
    const size_t N = x.size();
    if (N <= 1) return;

    // divide
    CArray even = x[std::slice(0, N/2, 2)];
    CArray  odd = x[std::slice(1, N/2, 2)];

    // conquer
    fft(even);
    fft(odd);

    // combine
    for (size_t k = 0; k < N/2;   k)
    {
        Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k];
        x[k    ] = even[k]   t;
        x[k N/2] = even[k] - t;
    }
}*/

This is my recreation attempt using dual list entries as complex numbers.

/// fft(ds_list_id)

// these lists are complex lists with the form [real,complex,real,complex,...,...]

var input = argument0;

// find how many complex numbers are in the pair list
N = ds_list_size(input)/2;
if (N <= 1)
    {
    return -1;
    }

// divide
even = ds_list_create();
for (var i=0; i<N; i =2)
    {
    ds_list_add(even,input[| i*2]);
    ds_list_add(even,input[| i*2 1]);
    };
odd = ds_list_create();
for (var i=1; i<N; i =2)
    {
    ds_list_add(odd,input[| i*2]);
    ds_list_add(odd,input[| i*2 1]);
    };

// conquer
var rollback = even;
if (fft(even) == -1)
    {
    even = rollback;
    }
rollback = odd;
if (fft(odd) == -1)
    {
    odd = rollback
    }

// combine
for (var k=0; k < N/2;   k)
    {
    var a = cos(-2*pi*k*2/N);
    var b = sin(-2*pi*k*2/N);
    var c = odd[| k*2];
    var d = odd[| k*2 1];

    var t_real = a*c - b*d; 
    var t_imag = a*d   b*c;

    input[| k*2    ]   = even[| k*2  ]   t_real;
    input[| k*2 1  ]   = even[| k*2 1]   t_imag;

    input[| k*2 N/2]   = even[| k*2  ] - t_real;
    input[| k*2 N/2 1] = even[| k*2 1] - t_imag;
    }

The input list is [1,1,1,1,0,0,0,0] should result in a [4,1,0,1,0,1,0,1] output but I am getting an output of [1,0,1,1,0,0,0,0]. Thanks again for any help. I can't figure it out and its 4am. I need sleep haha.