function spec = fft_rec(sig, N)
    if(size(sig)<N)
        sig(length(sig)+1 : N) = zeros(1,N-length(sig));
    end;
    if(size(sig) == 1)
        spec = sig(1);
        return;
    end
    odd_sig = sig(1:2:N);
    even_sig = sig(2:2:N);
    a = fft_rec(odd_sig, N/2);
    b = fft_rec(even_sig, N/2);
    WN = exp(-j*2*pi/N);
    k = 0:N/2-1;
    spec (1:N/2)= a + (WN.^k).*b;
    spec (N/2+1: N) = a - (WN.^k).*b;