Recursive_FFT(a){
              n <- length(a)
              if(n=1) return a

               w <- e^(2*pi*i/n)
               a[0] <- (a_0,a_1,......,a_(n/2-1))
               a[1] <- (a_n/2,a_(n/2 + 1),........,a_(n-1))

               y[0] <- Recursive_FFT(a[o])
               y[1] <- Recursive_FFT(a[1])

               for k <- 0 to n/2 -1
                         do begin
                             y_2k <- y_k[0] + y_k[1]
                             y_2k+1 <- y_k[0] - y_k[1]
                          end
               return y
          }

Faster FFTというがどれくらい高速なんでしょ