  Celestial amplitudes are flat-space amplitudes which are Mellin-transformed
to correlators living on the celestial sphere. In this note we present a
recursion relation, based on a tree-level BCFW recursion, for gravitational
celestial amplitudes and use it to explore the notion of conformal softness. As
the BCFW formula exponentiates in the soft energy, it leads directly to
conformal soft theorems in an exponential form. These appear from a soft piece
of the amplitude characterized by a discrete family of singularities with
weights $\Delta=1-\mathbb{Z}_+$. As a byproduct, in the case of the MHV sector
we provide a direct celestial analogue of Hodges' recursion formula at all
multiplicities.
