A recurrence relation (or recurrence) is an equation or inequality that describes a function in terms of its value on smaller inputs. We saw one in last example.

There are several methods for solving recurrence relations, including the substitution method, the recursion tree method and the master method.