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 recursive implementation of the cooley tukey get the elements at even odd indices
from cmath import exp, pi

def fft(x):
    
    N = len(x)
    if N == 1:
        return x

    
    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