# 3.2 Recursion and Induction

## Recursion

**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.

## Induction

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.