#Python, <strike>166</strike> <strike>151</strike> 150 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

    from math import*
    def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
    a+s*b/e**(2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

    >>> import numpy as np
    >>> x = np.random.random(512)
    >>> np.allclose(F(x), np.fft.fft(x))
    True