# 2.5: The FFT as a Recursive Evaluation of the DFT

It is possible to formulate the DFT so a length-\(N\) DFT can be calculated in terms of two length-(\(N/2\)) DFTs.

And, if \(N=2^{M}\) each of those length-(\(N/2\)) DFTs can be found in terms of length-(\(N/4\)) DFTs. This allows the DFT to be calculated by a recursive algorithm with \(M\) recursions, giving the familiar order \(N\log N\) arithmetic complexity.

Calculate the even indexed DFT values from the equation by:

\[C(2k)=\sum_{n=0}^{N-1}x(n)W_{N}^{2nk}=\sum_{n=0}^{N-1}x(n)W_{N/2}^{nk}\]

\[C(2k)=\sum_{n=0}^{N/2-1}x(n)W_{N}^{2nk}+\sum_{n=N/2}^{N-1}x(n)W_{N/2}^{nk}\]

\[C(2k)=\sum_{n=0}^{N/2-1}\left \{ x(n)+x(n+N/2)\right \}W_{N/2}^{nk}\]

and a similar argument gives the odd indexed values as:

\[C(2k+1)=\sum_{n=0}^{N/2-1}\left \{ x(n)-x(n+N/2)\right \}W_{N}^{n}W_{N/2}^{nk}\]

Together, these are recursive DFT formulas expressing the length-N DFT of \(x(n)\) in terms of length-N/2 DFTs:

\[C(2k)=DFT_{N/2}\left \{ x(n)+x(n+N/2)\right \}\]

\[C(2k+1)=DFT_{N/2}\left \{ [x(n)-x(n+N/2)]W_{N}^{n}\right \}\]

This is a “decimation-in-frequency" (DIF) version since it gives samples of the frequency domain representation in terms of blocks of the time domain signal.

A recursive Matlab program which implements this is given by:

A DIT version can be derived in the form:

\[C(k)=DFT_{N/2}\left \{ x(2n)\right \}+W_{N}^{k}DFT_{N/2}\left \{ x(2n+1)\right \}\]

\[C(k+N/2)=DFT_{N/2}\left \{ x(2n)\right \}-W_{N}^{k}DFT_{N/2}\left \{ x(2n+1)\right \}\]

which gives blocks of the frequency domain from samples of the signal.

A recursive Matlab program which implements this is given by:

Similar recursive expressions can be developed for other radices and and algorithms. Most recursive programs do not execute as efficiently as looped or straight code, but some can be very efficient, e.g. parts of the FFTW.

Note a length- \(2^M\) sequence will require \(M\) recursions, each of which will require \(N/2\) multiplications. This give the \(N\log N\)** **formula that the other approaches also derive.

### Contributor

- ContribEEBurrus