Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm.
Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).
def fft(x):
N = len(x)
if N == 1:
return x
assert N % 2 == 0
E = fft(x[::2])
O = fft(x[1::2])
X = [None] * N
for k in range(N // 2):
tf = np.exp(-2j * np.pi * k / N)
X[k] = E[k] + tf * O[k]
X[k + N//2] = E[k] - tf * O[k]
return X