Add Fast Fourier Transform (FFT) in R

[nachiket2005]

Overview

The fft_recursive function decomposes a DFT of size N into smaller DFTs of even and odd indexed elements, recursively combining their results.
If the input vector’s length is not a power of two, it is zero-padded to the next power of two for optimal performance.

This implementation serves as a clear, educational example of FFT internals while maintaining compatibility with complex input data.

---

Features

• Fully recursive Cooley–Tukey FFT implementation
• Accepts both numeric and complex input vectors
• Automatically zero-pads input to the next power of two
• Returns complex output representing frequency-domain components
• Compact and easy to understand — ideal for teaching and research use
• Includes example usage block for quick verification

---

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(N) (due to recursive calls and intermediate storage)