function  c=rft(n,x,w)

% c=rft(n,x,w)
% recurrence for fft, n=2^m, x = dim n, w, vector of nth roots of 1.
if n>2
  n=n/2;
  j=1:n;
  je=2*j;
  jo=2*j-ones(size(j));
  jn=j+n*ones(size(j));
  u=x(j)+x(jn);
  v=(x(j)-x(jn)).*w(j);
  z=w(jo);
  c(jo)=.5*rft(n,u,z);
  c(je)=.5*rft(n,v,z);
else
  c(1)=.5*(x(1)+x(2));
  c(2)=.5*(x(1)-x(2));
end