快速傅里叶（递归）

function F=fastf(gray)
tic
gray=double(gray);
[row,col] = size(gray);
rows = 2 ^nextpow2(row) ;
cols = 2 ^ nextpow2(col) ; 
F = zeros(rows,cols);
grays = zeros(rows,cols);
grays(1:row,1:col)=gray;
for x = 1:rows 
    F1(x,:) = ft_1D(grays(x,:))*rows; 
end
for y = 1:cols 
    F(:,y) = (ft_1D(F1(:,y).'))'*cols; 
end
toc
end

function F=ft_1D(gray_1D)
M=size(gray_1D,2);
if M==1
    F=gray_1D;
else
    N=M/2;
    grayeven_1D=gray_1D(2:2:end);
    Feven=ft_1D(grayeven_1D);
    grayodd_1D=gray_1D(1:2:end);
    Fodd=ft_1D(grayodd_1D);
    for k=0:N-1
        F(k+1)=( Feven(k+1)+Fodd(k+1)*exp(-1*i*2*pi*k/M))/2;
        F(k+N+1)=( Feven(k+1)-Fodd(k+1)*exp(-1*i*2*pi*k/M))/2;
    end
end
end