Recursion

Spotting one

The problem contains a smaller copy of itself. Reversing a list is reversing a shorter list and then attaching one item. Checking a tree is checking two smaller trees.

If you can describe the job in terms of the same job on something smaller, recursion fits.

Two parts, always

Every recursive solution has exactly two pieces, and missing either one is the usual cause of failure.

The stopping case is the smallest version, where you already know the answer without asking again. The shrinking step is how you make the problem smaller before asking again, so you are guaranteed to reach the stopping case.

Where to start

Factorial of a Number is the smallest possible example. It is only useful for seeing the two pieces clearly.

Reverse Linked List and Merge Two Sorted Lists next. Both are short, and both build their answer on the way back out of the recursion rather than on the way in, which is the first genuinely new idea here.

Pow(x, n) introduces halving. To raise a number to the twentieth power, raise it to the tenth and square it. Two calls collapse into one and a slow method becomes a fast one.

Validate Binary Search Tree teaches passing information downward. Each call needs to know the range its values are allowed to sit in, and that range comes from above.

Tower of Hanoi, Flatten a Multilevel Doubly Linked List and Unique Binary Search Trees II are the harder end. The last one builds every possible answer rather than one, which is a real step up.

Common mistakes

A stopping case that can never be reached. Checking for exactly zero while the value drops by two at a time, so it steps straight past.

Calling the function and throwing away the result. A recursive call you do not return or store does nothing at all.

Redoing the same work over and over. If the same small problem keeps turning up, the fix is to remember previous answers, and that is where dynamic programming starts.