Ведь все же в лоб получается из формулы для ДПФ:
SUM(x(n)*e^(-j*2pi*n*k/N)=SUM(x(2n)*e^(-j*2pi*2n*k/N))+SUM(x(2n+1)*e^(-j*2pi*(2n+1)*k/N)).

В древние времена, в конце 70-х годов, когда был студентом, сам по собственной дурости придумал этот алгоритм и реализовал его на Фортране, не знаю, во-первых, что он придуман и реализован до меня:-)
Были у нас по одному предмету учебно-исследовательские работы на предмет математического моделирования радиосистем. С написанием и обоснованием мат. модели, реализации ее на Фортране и прогонке фортрановской программы на кафедральной ЭВМ, коей была Наири-4.
Чтобы промоделировать мою радиосистему требовалось найти преобразование Фурье, до чего я допер махом. И махом его реализовал в лоб, без изысков, т.е. просто SUM(x(n)*e^(-j*2pi*n*k/N), N~=1000. Про БПФ я тогда не знал. Беда нагрянула неожиданно:-). Кафедральной машиной пользовалось несколько групп студентов, не считая преподавателей. Соответственно время счета студентам ограничивали. Вот мое творение в выделенное время не сосчиталось. И пришлось ускоряться. В процессе ускорения самостоятельно и дошел бо БПФ с прореживанием по времени и реализовал его, правда моя реализация, как я выяснил существенно позже, излишним изяществом не страдала, но работала она правильно и быстро:-)
Потом правда пришла другая беда - когда я стал докладать преподавателю о своих изысканиях в области БПФ, то он совершенно правильно посоветовал прекратить заниматься херней, быть проще и для начала обратиться к штатным кафедральным программисткам, которые мне непременно подскажут имя библиотечной функции быстрого преобр. Фурье:-). Что программистки и сделали:-)

В общем побольше куражу и все у Вас получится:-)