Optimize

This step is optional.

1.

It is often the case with recursive things that we don't really want to recurse all the way down to the silly case where we take the DFT of a single element. Rather, once we get to something small, we go ahead and calculate it directly, using dft.

2.

Modify your base case so that if N>2 it recurses, but when N=2 it calculates the DFT directly. Compare the run time to the original version. Experiment with different threshold values and find the optimum.