When you recursively split into $Y_{even}$ and $Y_{odd}$, from the second recursion onwards don't these sets have their even-ness and odd-ness violated? I.e., assume you are running the FFT algorithm on the first $Y_{even}$ (first time hitting step 5 below). The new $Y_{odd}$ in this recursive branch is made entirely of even terms. How does that not break the validity of $x*Y_{odd}$ being even, and thus the -f(x) giving you values for f(-x)?
My understanding was that this was a key assumption for that particular efficiency in the algorithm.
As a follow-on question: why do we need to pick roots of unity to build points from? I.e. why does using numbers which aren't the relevant roots of unity as x coordinates break the algorithm?
The algorithm I'm using is printed below for clarity:
