Recursion Can Be Weirder Than You Think
Too Long; Didn't Read
To solve your problem recursively, start by assuming you already solved the problem. Then, see how the big problem can be solved by solving one (or more) smaller problems. Decide what are your base cases, simple enough that they be solved directly, not requiring any more calls. At least for this problem, the four recipe steps are pretty straightforward. So, after following them I was greatly surprised when the simpler test cases passed without a problem. But to be honest, my surprise was how I was able to solve the problem and how I didn't know it worked.