 Solution

A return to zero is possible only at even times, andStirling's estimate makes this asymptotic to a positive constant timesA state is recurrent exactly when the sum of its return probabilities diverges. If $p=1/2$, the resulting $k^{-1/2}$ series diverges. If $p\ne 1/2$, then $4p(1-p)<1$ and the series converges geometrically. Thus the walk is recurrent exactly when $p=1/2$.