Why do you need to solve it with recursion? Is this an assignment/homework/coursework?
Anyway, all loops can be replaced with tail recursion, for a description of this see http://en.wikipedia.org/wiki/Tail_recursion