Make it recursive

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.

1.

Read the documentation for the if command in Maple. You have some choices regarding syntax, but I recommend something like the following:

fft:= proc (h, N)
  local x, y, z;
  if (N > 1) then

	(put the complicated thing here)

    H;
  else
    h;
  fi;
end:

2.

Recursive things can be hard to debug, so here are some suggestions:

(a)

Save your worksheet before you run the new routine. If you accidentally recurse infinitely, Maple might crash (although it shouldn't!).

(b)

Sneak up on it. If N=64, then try something like the following:

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.

(c)

Alternatively, you can start with smaller values of N and gradually increase the number of levels from the other direction.

3.

Time your program and compare it with the other timings. Try running FFTs and DFTs of different-sized signals (at least N=32, 64, and 128). Plot these points on a graph and comment on their trends.

4.

While you're at it, make a note of how the shape of the FFT changes depending on N.