# J, 62 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