Difficulty Implementing a Recursive Fast Fourier Transform in Python with Numpy
I'm trying to implement a recursive Fast Fourier Transform (FFT) algorithm in Python using Numpy, but I'm running into some issues with mismatched output sizes and unexpected results... My implementation is supposed to take a list of complex numbers and return their FFT, but when I test it, the output seems to be off by a factor of 2, and I also get an behavior about mismatched shapes. Here's what I have so far: ```python import numpy as np def fft(x): N = len(x) if N <= 1: return x even = fft(x[0::2]) # even indexed odd = fft(x[1::2]) # odd indexed T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)] return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)] x = [0, 1, 2, 3, 4, 5, 6, 7] # Example input fft_result = fft(x) print(fft_result) ``` When I run this, I get the output that doesn't match the expected FFT output for the input array. The initial parts of the output are fine, but the higher frequency components are incorrect. Additionally, I get a warning about the shapes not aligning in the last return statement. I've checked the base case, and it seems fine, but I suspect the scenario lies in how I'm combining the even and odd results. Any insights on what might be going wrong? I'm using Numpy version 1.21.0. I recently upgraded to Python latest. I'd really appreciate any guidance on this. My development environment is Ubuntu 20.04. Thanks for taking the time to read this!