另外一个重要的递归策略被称为backtracking（中文为回溯）。
A backtracking algorithm tries to construct a solution to a computational problem incrementally, one small piece at a time. Whenever the algorithm needs to decide between multiple alternatives to the next component of the solution, it recursively evaluates every alternative and then chooses the best one.
Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints. Often (but not always) this goal is itself a sequence.
In each recursive call to the backtracking algorithm, we need to make exactly one decision, and our choice must be consistent with all previous decisions.
Thus, each recursive call requires not only the portion of the input data we have not yet processed, but also a suitable summary of the decisions we have already made. For the sake of efficiency, the summary of past decisions should be as small as possible.
When we design new recursive backtracking algorithms, we must figure out in advance what information we will need about past decisions in the middle of the algorithm. If this information is nontrivial, our recursive algorithm might need to solve a more general problem than the one we were originally asked to. （例如，我们想要找到一个无序数组中的中位数，我们的算法解决了一个更普适的问题：找到该无序数组中的 kth smallest element for arbitrary k.）
Finally, once we've figured out what recursive problem we really need to solve, we solve that problem by recursive brute force: Try all possibilities for the next decision that are consistent with past decisions, and let the Recursion Fairy worry about the rest. Do not be clever here. Do not skip "obviously" stupid choices. Try everything. You can make the algorithm faster later.