fft算法递归与非递归

FFT（快速傅里叶变换）算法是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法。FFT算法主要包括递归和非递归两种实现方式。

递归实现的FFT算法通常被称为“分裂基FFT算法”，它将一个较大的DFT问题分解成两个较小的DFT问题，这两个问题通常是原问题大小的一半。递归过程会一直进行下去，直到达到可以直接计算的最小子问题为止。最典型的递归FFT算法是Cooley-Tukey算法，它要求数据点数为2的幂次。

非递归FFT算法，也称为迭代FFT算法，是通过直接操作数据的索引来实现FFT变换，通常利用位反转（bit-reversal）技术对数据进行重新排列，然后按照特定的顺序进行蝶形运算。这种方法避免了递归的开销，对于较大的数据集来说，其性能优于递归FFT算法。