Hi Nikolay,
sorry, I have no idea what is going wrong. But I have written a minimal recursive fft implementation - i guess this is what you are having in mind with your sketch?!? (just for demonstration purposes, functions can digest only lists of length 2^n, not optimized in any way!). But maybe this is helpful though:
ClearAll["Global`*"]
fourier[fl_List] :=
Module[{length, eleOdd, eleEven, fouOdd, fouEven, phase},
If[(length = Length[fl]) == 1, Return[Sow@fl]];
{eleOdd, eleEven} = Transpose[Partition[fl, 2]];
fouOdd = fourier[eleOdd];
fouOdd = Flatten[{fouOdd, fouOdd}];
fouEven = fourier[eleEven];
fouEven = Flatten[{fouEven, fouEven}];
phase = Table[Exp[-(2 Pi I) n/length], {n, 0, length - 1}];
Sow[fouOdd + fouEven phase]
]
invfourier[fl_List] :=
Module[{length, eleOdd, eleEven, fouOdd, fouEven, phase},
If[(length = Length[fl]) == 1, Return[Sow@fl]];
{eleOdd, eleEven} = Transpose[Partition[fl, 2]];
fouOdd = invfourier[eleOdd];
fouOdd = Flatten[{fouOdd, fouOdd}];
fouEven = invfourier[eleEven];
fouEven = Flatten[{fouEven, fouEven}];
phase = Table[Exp[(2 Pi I) n/length], {n, 0, length - 1}];
Sow[(fouOdd + fouEven phase)/2]
]
and then:
Regards -- Henrik