Recurrence relation

A recurrence relation is a formula that expresses the cost of a problem through the cost of smaller problems of the same kind and the work done outside those subproblems.