Wikipedia presents butterfly as "a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data-flow diagram in the radix-2 case ..."

The question is: What was the first time that FFT was represented by *Butterfly Diagram* ? References would be appreciated.

Digital Signal Processing, Prentice Hall, 1975, Fig. 6.3, pp. 291, presents a "Flow graph of... DFT computations (N=8)". Fig. 6.8, pp. 296, "Flow graph of basic butterfly computation...". – Papiro Jun 4 '12 at 17:50