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.