In the gauge-theoretic formulation of gravity the cubic vertex becomes simple enough for some graviton scattering amplitudes to be computed using the Berends-Giele-type recursion relations. We present such a computation for the current with all same helicity on-shell gravitons. Once the recursion relation is set up and low graviton number cases are worked out, a natural guess for the solution in terms of a sum over trees readily presents itself. The solution can also be described either in terms of the half-soft function familiar from the 1998 paper by Bern, Dixon, Perelstein and Rozowsky or as a matrix determinant similar to one used by Hodges for MHV graviton amplitudes. This solution also immediately suggests the correct guess for the MHV graviton amplitude formula, as is contained in the already mentioned 1998 paper. We also obtain the recursion relation for the off-shell current with all but one same helicity gravitons.