I would suggest instead of getting into a solution to particular problem you should understand how recursion is done and I would suggest you read
Recursion - Begining
Types of Recursion - Advanced