Your problem has known solutions to simple inputs. A recursive function calls itself again and again until it reaches a solution. There are two steps:
Base case: a known solution to a simple input
Recursive case: calls the function with a simpler or smaller input
When the base case is met the recursive loop is terminated and a solution is derived.