recursiveifft.m

通过迭代算法来实现快速付立叶变换

function y=RecursiveIFFT(a)             %递归IFFT   
n=length(a);                            %向量的长度
if n==1
    y=a;                                %递归出口
else
    wn=complex(cos(2*pi/n),sin(2*pi/n));%主n次单位根
    w=1;
    a0=a(1:2:n);
    a1=a(2:2:n);
    y0=RecursiveIFFT(a0);                    %分治，计算IDFT------n/2
    y1=RecursiveIFFT(a1);                     %分治，计算IDFT------n/2
    for k=1:n/2
        y(k)=y0(k)+w*y1(k);                  %组合结果      
        y(k+n/2)=y0(k)-w*y1(k);              %组合结果
        w=w*wn;
    end
end