Implementation of the CooleyTukey, which is the most common FFT algorithm. Input: an array of complex values which has a size of N, where N is an integer power of 2 Output: an array of complex values which is the discrete fourier transform of the input Example 1 Input: 2.02j, 1.03j, 3.01j, 2.02j Output: 88j, 2j, 22j, 20j Pseudocode: https:en.wikipedia.orgwikiCooleyE28093TukeyFFTalgorithm Recursive implementation of the CooleyTukey N  lenx if N  1: return x get the elements at evenodd indices even  fftx0::2 odd  fftx1::2 y  0 for i in rangeN for k in rangeN2: q  exp2jpikNoddk yk  evenk  q yk  N2  evenk  q return y
from cmath import exp, pi

def fft(x):
    """ Recursive implementation of the Cooley-Tukey"""
    N = len(x)
    if N == 1:
        return x

    # get the elements at even/odd indices
    even = fft(x[0::2])
    odd = fft(x[1::2])

    y = [0 for i in range(N)]
    for k in range(N//2):
        q = exp(-2j*pi*k/N)*odd[k]
        y[k] = even[k] + q
        y[k + N//2] = even[k] - q

    return y
