#Cooley-Tukey

{.,.({[\.2%fft\(;2%fft@-1?-1\?-2?:w;.,,{w\?}%[\]zip{{*}*}%]zip.{{+}*}%\{{-}*}%+}{;}if}:fft;

[1 1 1 1 0 0 0 0]fft n*