??? - But it does result in the original sequence:

Regards -- Henrik

EDIT: Sorry, I missed that you were talking about WolframAlpha ...

You can use https://www.open.wolframcloud.com

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

Hi Henrik,

Thanks. Yep, there is the issue - aside from not performing any scaling on my result, I get the same thing, but the 2nd and the last element are switched. What am I doing wrong in this DIT FFT butterfly?

Cheers.

Thanks so much, Leonardo!

Thanks to Henrik and Sam, also.