Overview
A recurrence is an equation or inequality that describes a function in terms of its value on
smaller inputs.[1] In general, there are two operations you need to reckon of
when you are dealing with a recurrence relation. Those two operations are
the base case and the general case. The base case is sometimes an O(1)
constant-time operation, though it can be otherwise; A general case decomposes the
current problem into one or more smaller subproblems. Thus, we recursively
solve the subproblem and combine the sub-solutions bottom-up to solve
the original problem. A good example of recursion is the Factorial function
(equation 1.2.23), or the recurrence function of Merge Sort (of equation
3.9.2).
In general, there are three methods toward solving a recurrence problem: