[Python] I can't understand recursive part of FFT in Python

So basically I have this code of FFT implemented in Python for 2^m samples.

def fft(x):
N = len(x)
if N == 1:
return x
even = fft(x[0::2])
odd = fft(x[1::2])

result = [0] * N
for k in range(N // 2):
twiddle = cmath.exp(-2j * math.pi * k / N) * odd[k]
result[k] = even[k] + twiddle
result[k + N // 2] = even[k] - twiddle
return result


Now in Cooley-Tukey's algorithm we split Samples into odd and even and apply DFT on each sample recursively, like this -



As you can see, we need to Multiply Even and odd with

But in our code we multiply Odd[k] with cmath.exp(-2j * math.pi * k / N) which is just twiddle factor (which we multiply with summation of Odd DFT). Which doesn't make any sense to me. Like we also need to multiply Even and Odd with

I heard people saying it does this recursively, but how?

Btw, is it right to ask this question here? or should I ask this in Math Stack Exchange?

Continue reading...