recursive_fft.js

    var calculateFFT = function(real, imag) {
      var bufferSize = real.length;
        
      if ( bufferSize == 1 ) {
        return [[real[0], imag[0]]];
      }
        
      if(bufferSize % 2 != 0) throw "Invalid buffer size, length must be an even number";
        
      var even_real = [];
      var even_imag = [];
      var odd_real = [];
      var odd_imag = [];
        
      // break up signal into odd and even parts
      for ( var k = 0; k < bufferSize/2; k++ ) {
        if ( real != null && imag != null ) {
          even_real[k] = real[2*k];
          even_imag[k] = imag[2*k];
          odd_real[k] = real[2*k+1];
          odd_imag[k] = imag[2*k+1];
        } else { 
          // this is a non complex signal
          even_real[k] = real[2*k];
          even_imag[k] = 0.0;
          odd_real[k] = real[2*k+1];
          odd_imag[k] = 0.0;
        }
      }
        
      var q = calculateFFT(even_real, even_imag);
      var r = calculateFFT(odd_real, odd_imag);

      y = [];

      for ( var k = 0; k < bufferSize/2; k++ ) {
        var kth = -2 * k * Math.PI / bufferSize;
        var wk_real = Math.cos(kth);
        var wk_imag = Math.sin(kth);

        // Complex: q[k] + wk * r[k], must remember to multiply the complex parts correctly
        y[k] = [q[k][0] + (wk_real*r[k][0] - wk_imag*r[k][1]),
                q[k][1] + (wk_real*r[k][1] + wk_imag*r[k][0])];

        // Complex: q[k] - wk * r[k], must remember to multiply the complex parts correctly
        y[k + bufferSize/2] = [q[k][0] - (wk_real*r[k][0] - wk_imag*r[k][1]),
                               q[k][1] - (wk_real*r[k][1] + wk_imag*r[k][0])];
      }
      return y;
    }