That's an excellent explanation - comprehensive and detailed. The only complaint I have is against:
(1) make absolutely sure that every time the function calls itself, it's calling itself on a STRICTLY SMALLER subproblem
While that generally will work, there are cases where it doesn't: namely, those cases where there is no calculable end to the recursion. Take for example a floodfill algorithm: For each adjacent pixel that is of the same colour, you recurse down that path setting the new colour as you go. Note that this does not break the problem into smaller sub-problems; although it branches, the problem is identical at each step in the recursion (unless you count the overall state of the program at which the function is executed) until at some point none of the surrounding pixels are of the target colour, and the function then returns.
