Recursion is a general problem solving strategy that involves taking a problem and decomposing it into smaller sub-problems. By doing so, we can break down something that seems daunting into something that we are more confident solving. We saw some examples of recursion when we wrote list algorithms, but now we will approach this topic in a formal manner.
Closely related to recursion is induction, which is a proof technique used in mathematics. In order to be absolutely confident in a recursive algorithm, we must mathematically prove that our algorithm works.