下面，我们分别定义两个长为N/2的子序列

　　它们对应的N/2点DFT如下

　　这样，序列x(n)的N点DFT就可以通过下面的式子计算

　　那么这个式子说明什么问题呢？好好想想。提示一下，X((k)是N点DFT，而计算它的G(k)和H(k)则都是N/2点DFT，只要计算出了G(k)和H(k)，就可以用上面的加法来计算X(k)了，而计算G(k)和H(k)时都只要用N/2点DFT就行了，这样问题就归结为计算这两个子序列了，那么又如何计算G(k)和H(k)呢？…… 啊！想想程序设计中的"递归"的思想吧。你会得到答案的。……