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