Modern on-shell S-matrix methods may dramatically improve our understanding of perturbative quantum gravity, but current foundations of on-shell techniques for General Relativity still rely on off-shell Feynman diagram analysis. Here, we complete the fully on-shell proof of Ref.~\cite{ST} that the recursion relations of Britto, Cachazo, Feng, and Witten (BCFW) apply to General Relativity tree amplitudes. We do so by showing that the surprising requirement of "bonus" $z^{-2}$ scaling under a BCFW shift directly follows from Bose-symmetry. Moreover, we show that amplitudes in generic theories subjected to BCFW deformations of identical particles necessarily scale as $z^{\rm even}$. When applied to the color ordered expansions of Yang-Mills, this directly implies the improved behavior under non-adjacent gluon shifts. Using the same analysis, three-dimensional gravity amplitudes scale as $z^{-4}$, compared to the $z^{-1}$ behavior for conformal Chern-Simons matter theory.