ABSTRACT
Sequences, also known as functions of a discrete variable, appear in many applications of computer science, in numerical analysis, and, naturally, in discrete mathematics. A recurrence is an equation that describes the evolution or behavior of such a function. In this chapter, the authors present many such equations, and solve only a few special types. Many useful algorithms lead to recurrences with "integer functions." The divide-and-conquer approach is a top-down approach because the solution to a top level instance of a problem is obtained by going down and obtaining solutions to smaller instances. In general, there is no algorithm to solve recurrences, but there are classes for which people have methods that work. Recursive binary search is one of the simplest and best-known divide-and-conquer algorithms. Like the binary search, merge sort is conceptually one of the simplest sorting algorithms and is based on the divide-and-conquer approach.
