# J, <s>86</s> <s>62</s> <s>54</s> 49 bytes

    ]`((#~((+,-)(%_1^i.@#%#))&$:(#~-.))1:`0:\)@.(1<#)

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

Saved 4 bytes using *e*<sup>*πi*</sup> = -1, thanks to @[Leaky Nun](http://codegolf.stackexchange.com/users/48934/leaky-nun).

## Usage

       f =: ]`((#~((+,-)(%_1^i.@#%#))&$:(#~-.))1:`0:\)@.(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

## Explanation

    ]`((#~((+,-)(%_1^i.@#%#))&$:(#~-.))1:`0:\)@.(1<#)

    ]`(...)@.(1<#)
             (1<#) Checks if the input list length is greater than one
    ]              Identity function, returns the input list
      (...)        Recurse on input list

    (...)1:`0:\
              \ Applys a verb to all prefixes of the input list
         1:`0:  Cycles between two constant function, return 1 or 0
                Creates a mask where even indexes are 1 and odd are 0
    (...)       Operate on the input list and the even index mask

    #~(...)&$:(#~-.)

    #~               Select the even index values from the input list
                 -.  Complement the mask to select odd indexes
               #~    Select the odd index values from the input list
           &$:       Call recursively on only even indexes and only odd indexes
      (...)          Combine the two halves

    (+,-)(%_1^i.@#%#)
                 #    Get length of odd list
              i.@     Create range from 0 to the odd length exclusive
                   #  Get length of odd list
                  %   Divide each value in the range by the length of the odd list
           _1^        Compute (-1)^x for each x in the modified range
          %           Divide each value in the odd list by the computed values
     +                Add elementwise between the even values and modified odd values
       -              Subtract elementwise between the even values and modified odd values
      ,               Join the two lists