Why is this recursive DFT algorithm not equivalent to this iterative method? Edit 1/30 - Taking @Fat32's edits into account, it seems like there is still an issue with the scale of the frequency axis. While version 2 correctly identifies the response at 1 HZ, version 1 seems to be covering a frequency range of 1/T.

I'd like version 1 to cover the same range of frequencies as version 2. Can anyone help with this?



(End edit 1/30)

--

I have 2 DFT algorithms that I would expect to return same frequency response. Unfortunately, the more efficient recursive algorithm does not seem to behave as expected.

Version 1 - Efficient Divide and Conquer method, but output is incorrect:

function [ s ] = DFT_ver_1( x )

N = length(x);

if N == 1
    s = x(1);
    return;
else

X1 = DFT_ver_1(x(1:2:N));
X2 = DFT_ver_1(x(2:2:N)); 
s = zeros(N,1);

for k = 1:(N/2)
        W(k)     = exp(-1j*2*pi*(k + 1)/N);
        s(k)     = X1(k) + W(k) * X2(k);
        s(k+N/2) = X1(k) - W(k) * X2(k);  
end


Version 2 - Inefficient, but generates expected results:

function [ s ] = DFT_ver_2( x , f, n)

N = length(x);

b = zeros(N,N);
b_1 = -2*pi*(f/N);

for idx = 1 : N
for jdx = 1 : N
    b(jdx, idx) = b_1(idx) * n(jdx);
end
end

anlyz_fn = cos(b) + 1i * sin(b);
s = single(zeros(N,1));

for k = 1 : N
    val = 2 * sum(anlyz_fn(k,:) * x.');
    s(k) = val;
end

end


I would expect both algorithms to return the same result. However, this does not appear to be the case. 

You can see that the bottom plot (version 2) shows the correct frequency response to a 1 HZ signal, but the middle (version 1) does not:



Code to run both:

       T  = single(3.20); % (sec) time window
       dt = single(0.05); % (sec) sample time
        N = T / dt;          % (ct) num samples
        n = 0 : N - 1;       % (ct) bucket index vector
        t = 0 : dt : T - dt; % (sec) time vector
smpl_freq = 1 / dt;          % (Hz) sampling frequency
 freq_res = smpl_freq / N;   % (Hz) frequency resolution
        f = n * freq_res;    % (Hz) freq. bucket vector

x_t = sin( 2*pi*t );

subplot(3,1,1);
plot(t, x_t);
xlabel('Sample Time (sec)');
ylabel('Magnitude');

subplot(3,1,2);

s_v1     = DFT_ver_1( x_t); %, f, n );
s_v1_mag = abs( s_v1(1:N/2) )/N; 

stem(f(1:N/2)/T, s_v1_mag);

xlabel('Freq. Response (Hz) v1');
ylabel('Magnitude');

s_v2     = DFT_ver_2( x_t , f, n );
s_v2_mag = abs( s_v2(1:N/2) )/N; 

subplot(3,1,3);
stem(f(1:N/2) / T , s_v2_mag);
xlabel('Freq. Response (Hz) v2');
ylabel('Magnitude');
All right, you made two small mistakes and here is the corrected version: (I changed your function's name). Btw, you can get rid of the for loop too... ;-) 

function [ s ] = recDFT2( x )
%
% a recursive DFT
%


N = length(x);

if N == 1
    s = x(1);
    return;
else

    X1 = recDFT2(x(1:2:N));
    X2 = recDFT2(x(2:2:N)); 
    s = zeros(N,1);

    for k = 1:(N/2)
        W(k)     = exp(-1j*2*pi*(k - 1)/N);
        s(k)     = X1(k) + W(k) .* X2(k);
        s(k+N/2) = X1(k) - W(k) .* X2(k);  
    end
end