;Task:
Calculate the &nbsp; FFT &nbsp; (<u>F</u>ast <u>F</u>ourier <u>T</u>ransform) &nbsp; of an input sequence.

The most general case allows for complex numbers at the input 
and results in a sequence of equal length, again of complex numbers. 
If you need to restrict yourself to real numbers, the output should 
be the magnitude &nbsp; (i.e.: &nbsp; sqrt(re<sup>2</sup> + im<sup>2</sup>)) &nbsp; of the complex result. 

The classic version is the recursive Cooley–Tukey FFT. [http://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm Wikipedia] has pseudo-code for that. 
Further optimizations are possible but not required.
<br><br>