(Basic) Recursive and Vectorized Fast Fourier Transform

basicFFT is a basic implementation of the discrete FFT algorithm, for teaching purposes. It is recursive and vectorized, hence pretty fast.

This is a very simple, yet easy to read, imlementation of the (discrete)

Fast Fourier Transform.

Still, the code is easy to read (being it the recursive version of the FFT),

and fast (being it vectorized, i.e., it does not use for loops).

WARNING! This algorithm works only when the input vector has length equal to a power of 2.

If the length of your input is not a power of two, or you want a better speed,

then use the Matlab builtin function 'fft'.

This implementation is mainly intented for teaching purposes, even if is rather fast

due to vectorization.

More info at:

The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? - YouTube

Fast Fourier transform - Competitive Programming Algorithms (cp-algorithms.com)