快速傅里叶变换（FFT）是一种高效的算法，用于计算离散傅里叶变换（DFT）。FFT算法基于递归地将大的DFT分解为更小的DFT，从而减少计算复杂度。本文将介绍FFT的两种实现方式：递归和非递归。
递归FFT算法基于傅里叶变换的主要公式，通过递归地将DFT分解为更小的DFT来实现。这种方法易于理解，但在某些环境下可能因为递归调用的限制而不太适用。
FFT算法的核心思想是将DFT分解为更小的DFT，直到只剩下两个样本。例如，对于8个样本的DFT，首先将其分解为两个4个样本的DFT，然后继续分解，直到每个DFT只有两个样本。
public void CalcSubFFT(TKomplex[] a, int n, int lo) {
int i, m;
TKomplex w;
TKomplex v;
TKomplex h;
if (n > 1) {
Shuffle(a, n, lo);
m = n / 2;
CalcSubFFT(a, m, lo);
CalcSubFFT(a, m, lo + m);
for (i = lo; i < lo + m; i++) {
w.real = Math.Cos(2.0 * Math.PI * (double)(i - lo) / (double)(n));
w.imag = Math.Sin(2.0 * Math.PI * (double)(i - lo) / (double)(n));
h = kprod(a[i + m], w);
v = a[i];
a[i] = ksum(a[i], h);
a[i + m] = kdiff(v, h);
}
}
}
为了提高计算效率，可以将正弦和余弦值预先计算并存储在查找表中，从而避免在每次计算时重复计算这些值。
for (i = 0; i < (N / 2); i++) {
we[i].real = Math.Cos(2.0 * Math.PI * (double)(i) / (double)(N));
we[i].imag = Math.Sin(2.0 * Math.PI * (double)(i) / (double)(N));
}
非递归FFT算法避免了递归调用，适用于不支持递归调用的环境。虽然实现起来相对复杂，但可以减少计算时间。
非递归FFT算法通过迭代地计算DFT，而不是递归地分解。这种方法需要进行位反转操作，以确保样本的正确顺序。
public void BitInvert(TKomplex[] a, int n) {
int i, j, mv = n/2;
int k, rev = 0;
TKomplex b;
for (i = 1; i < n; i++) {
k = i;
mv = n / 2;
rev = 0;
while (k > 0) {
if ((k % 2) > 0) rev = rev + mv;
k = k / 2;
mv = mv / 2;
}
if (i < rev) {
b = a[rev];
a[rev] = a[i];
a[i] = b;
}
}
}
we = new TKomplex[N / 2];
for (i = 0; i < (N / 2); i++) {
we[i].real = Math.Cos(2 * Math.PI * (double)(i) / (double)(N));
we[i].imag = Math.Sin(2 * Math.PI * (double)(i) / (double)(N));
}