# Matlab, <s>128</s> <s>118</s> <s>107</s> <s>104</s> <s>98</s> 97

EDIT4: Yay, -1 character more (could aslo have done without the `k`):

    function Y=f(Y)
    n=numel(Y);  
    if n>1;
       k=2:2:n;
       c=f(Y(k-1));
       d=f(Y(k)).*(-1).^(-(k'/2-1)*2/n);
       Y=[c+d;c-d];
    end


EDIT2/3: Thanks for @sanchises for further improvements!

    function Y=f(Y)
    n=numel(Y);  
    if n>1;
       c=f(Y(1:2:n));
       d=f(Y(2:2:n)).*(-1).^(-(0:n/2-1)*2/n).';
       Y=[c+d;c-d]; 
    end


EDIT: Could make some improvements, and noticed that the scaling constant is not required.

This is the expanded version, character count is valid if you remove the newlines/spaces. (Works only for column vectors.)

    function y=f(Y)
    n=numel(Y);  
    y=Y;
    if n>1;
       c=f(Y(1:2:n));
       d=f(Y(2:2:n));
       n=n/2;
       d=d.*exp(-pi*i*(0:n-1)/n).';
       y=[c+d;c-d]; 
    end