Too Fast, Too Fourier: FFT Code Golf
Mathematica, 95 bytes

Another implementation of the Cooley–Tukey FFT with help from @chyaong.

{n=Length@#}~With~If[n&gt;1,Join[+##,#-#2]&amp;[#0@#[[;;;;2]],#0@#[[2;;;;2]]I^Array[-4#/n&amp;,n/2,0]],#]&amp;


Ungolfed

FFT[x_] := With[{N = Length[x]},
  If[N &gt; 1,
    With[{a = FFT[ x[[1 ;; N ;; 2]] ], 
          b = FFT[ x[[2 ;; N ;; 2]] ] * Table[E^(-2*I*Pi*k/N), {k, 0, N/2 - 1}]},
      Join[a + b, a - b]],
    x]]