Implement the transformation explained on page 408. Divide
the array into evens and odds, and use the dft procedure to find
the DFT of each half. Then stich the two halves into the DFT of
the original array.
HINT: the tricky thing here is that the two sub-DFTs are only half
as long as the original, so you have to double them up by repeating
them (or by taking the indices mod N/2).
