The goal here is to make fft recursive by making it invoke itself instead of dft. In order to make that work, though, we have to avoid the possibility of infinite recursion by checking for a base case and terminating early (without making the recursive call) when we get there.
The base case for FFT is when the length of the array is 1, in which case the result is just the array itself.
fft:= proc (h, N) local x, y, z; if (N > 1) then (put the complicated thing here) H; else h; fi; end:
fft:= proc (h, N) local x, y, z; if (N > 32) then (put the complicated thing here) H; else dft(h,N); fi; end:
In other words, at the top level of the recursion (N=64), we do the divide, conquer and glue thing. But at the next level down we go ahead and use the dft procedure. Using this code, you can gradually increase the number of levels of recursion.