## Python 3: <strike>140</strike> <strike>134</strike> 113 characters

Short version - short and sweet, fits in a tweet (with thanks to [miles](https://codegolf.stackexchange.com/users/6710/miles)):

<!-- language-all: lang-python -->

    from math import*
    def f(v):
     n=len(v)
     if n<2:return v
     a,b=f(v[::2])*2,f(v[1::2])*2;return[a[i]+b[i]/1j**(i*4/n)for i in range(n)]

(In Python 2, `/` is truncating division when both sides are integers. So we replace `(i*4/n)` by `(i*4.0/n)`, which bumps the length to 115 chars.)

Long version - more clarity into the internals of the classic Cooley-Tukey FFT:

    import cmath
    def transform_radix2(vector):
        n = len(vector)
        if n <= 1:  # Base case
            return vector
        elif n % 2 != 0:
            raise ValueError("Length is not a power of 2")
        else:
            k = n // 2
            even = transform_radix2(vector[0 : : 2])
            odd  = transform_radix2(vector[1 : : 2])
            return [even[i % k] + odd[i % k] * cmath.exp(i * -2j * cmath.pi / n) for i in range(n)]