fft[{x_}] := {N@x}
fft[l__] :=
 Join[#, #] &@fft@l[[1 ;; ;; 2]] +
  Exp[(-2 \[Pi] I)/Length@l (Range@Length@l - 1)] (Join[#, #] &@
     fft[l[[2 ;; ;; 2]]])

fft[{1, 1, 1, 1, 0, 0, 0, 0}] // Column