Some problems are best solved by being broken into pieces. Entire cakes are hard to eat in a single sitting, but cut them up into a bunch of little slices and they're sure to disappear.

(Especially when you want to fool people into thinking it's more than just Shmoop eating the cake.)

But how do we know, for sure, that recursion works and works well?

Formal proofs using recursion—called induction, BTW—can help show where recursion works, but we aren't going to get into them right now because they rely on some axioms about integers. The main take away is that recursion's a bit of a trust fall. As long as your algorithm can cover every possible input/output appropriately, you can trust that it'll work.

Easier said than done.

The vast majority of recursive problems are going to deal with three possible categories of inputs:

• Values greater than the base case (both even and odd)
• Numbers less than the base case (both even and odd)
• The base case

As long as you can always account for all of these situations, your recursion won't run infinitely. Sometimes. If your recursive step adds or subtracts more than one from the value, there'll still be holes.

Sorry, that's the best we can promise you. If you want to make sure the recursion works the way it should in every situation, you might just have to make a formal, inductive proof.

…Or you could just test the formula on values greater than, less than, and equal to the base case and make an educated guess that it'll work for all outputs.

Recursion (and iteration for that matter) work because these little sub-problems are so much easier—not to mention faster—to deal with than the entire problem. Iteration works by applying the same procedure to each subproblem until it solves the whole problem. Recursion does this too, but gets some extra power from the fact that all of these subproblems are interconnected. In a recursive loop, the next step is entirely dependent on the results of the previous one, which isn't necessarily true of an iterative loop.

One of the biggest pitfalls of using loops of any kind—recursion or iteration—is designing them poorly so they get carried away and never stop (i.e. you forgot to account for a specific input). Recursion works when you, the recursion master, make it work.

After all, recursion and iteration are just more tools in a programmer's toolbox. You can make programs work without them, but…why?