Too Fast, Too Fourier: FFT Code Golf Implement the Fast Fourier Transform in the fewest possible characters.
Rules:

Shortest solution wins

It can be assumed that the input is a 1D array whose length is a power of two.

You may use the algorithm of your choice, but the solution must actually be a Fast Fourier Transform, not just a naive Discrete Fourier Transform (that is, it must have asymptotic computation cost of \$O(N \log N)\$)

the code should implement the standard forward Fast Fourier Transform, the form of which can be seen in equation (3) of this Wolfram article,


$$F_n = \sum_{k=0}^{N-1}f_ke^{-2\pi ink/N}$$

Using an FFT function from a pre-existing standard library or statistics package is not allowed.  The challenge here is to succinctly implement the FFT algorithm itself.
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]]