J, 63 bytes

]`([:({.((+,-)(%r.@o.@(%~i.)@#))&$:{:)]{~-:@#|:@i.@,2:)@.(#>1:)

An improvement after a few years. Still uses the Cooley-Tukey FFT algorithm.

Usage

   f =: ]`([:({.((+,-)(%r.@o.@(%~i.)@#))&$:{:)]{~-:@#|:@i.@,2:)@.(#>1:)
   f 1 1 1 1
4 0 0 0
   f 1 2 3 4
10 _2j2 _2 _2j_2
   f 5.24626 3.90746 3.72335 5.74429 4.7983 8.34171 4.46785 0.760139
36.9894 _6.21186j0.355661 1.85336j_5.74474 7.10778j_1.13334 _0.517839 7.10778j1.13334 1.85336j5.74474 _6.21186j_0.355661