Trace

Interactive FFT Trace

Step through recursive and iterative FFT on an 8-point input, with live variable inspection and highlighted code.

The recursive FFT (Cooley-Tukey) solves DFT in O(n log n) by divide-and-conquer. It splits the input in half, recurses on each half independently, then merges the results with a butterfly operation.

1

Split

Separate even-indexed and odd-indexed coefficients into two halves.

2

Recurse

Recursively compute the DFT of each half — the tree reaches depth log₂ n.

3

Butterfly

Combine: X[k] = E[k] + ω·O[k] and X[k+n/2] = E[k] − ω·O[k], where ω = e^(−2πi/n).

Input: [1, 1, 0, 0, 0, 0, 0, 0] (coefficients of 1+x, zero-padded to 8 points)

Step Legend

call

Entering a recursive FFT subproblem

base case

n = 1 — single element is its own DFT

split

Separating even & odd indexed coefficients

butterfly

Butterfly: combining two half-DFTs via twiddle factor

return

Returning the combined result up the call stack

Visualization

n = 8start = 0n = 4start = 0n = 4start = 4n = 2start = 0n = 2start = 2n = 2start = 4n = 2start = 6n = 1start = 0n = 1start = 1n = 1start = 2n = 1start = 3n = 1start = 4n = 1start = 5n = 1start = 6n = 1start = 7d=0d=1d=2d=3

Step Explanation

fft(n=8, start=0)

Entering FFT on subarray of length 8 starting at index 0. We will recursively split this into even- and odd-indexed elements.

Variables

NameValue
n8
depth0
start0
stack depth1
step kindcall

Code

1function fft(a, inv = false) {Enter: FFT on subarray of length n
2  const n = a.length;Store the current subarray length
3  if (n === 1) return a;           // base caseBase case — single element is its own DFT
4  const even = a.filter((_, i) => i % 2 === 0);Extract even-indexed coefficients → A_even
5  const odd  = a.filter((_, i) => i % 2 !== 0);Extract odd-indexed coefficients → A_odd
6  const E = fft(even, inv);Recurse on the even half
7  const O = fft(odd,  inv);Recurse on the odd half
8  const out = new Array(n);Allocate combined output array
9  for (let k = 0; k < n/2; k++) {Butterfly combine loop  (k = 0 … n/2 − 1)
10    const w = omega(k, n, inv);    // twiddle factorCompute twiddle factor  ω^k_n = e^{−2πik/n}
11    out[k]       = E[k] + w * O[k];Upper output:  X[k]     = E[k] + ω · O[k]
12    out[k + n/2] = E[k] - w * O[k];Lower output:  X[k+n/2] = E[k] − ω · O[k]
13  }End butterfly loop
14  return out;Return combined DFT result up the call stack
15}End of function
Step 1 of 49