recursivefft.m

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

function y=RecursiveFFT(a)             %递归FFT
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=RecursiveFFT(a0);                     %分治，计算DFT------n/2
    y1=RecursiveFFT(a1);                     %分治，计算DFT------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