Applied Discrete Structures

Here is a recursive definition of binomial coefficients, which we introduced in Chapter 2.

We refer to \(x\) as a variable here, although the more precise term for \(x\) is an indeterminate. There is a distinction between the terms indeterminate and variable, but that distinction will not come into play in our discussions.

Zeroth degree polynomials are called constant polynomials and are simply elements of the set of coefficients.

A count of the number of operations performed shows that five multiplications and three additions/subtractions were performed. The first two multiplications compute \(7^2\) and \(7^3\text{,}\) and the last three multiply the powers of 7 times the coefficients. This gives you the four terms; and adding/subtracting a list of \(k\) numbers requires \(k-1\) addition/subtractions. The following definition of a polynomial expression suggests another more efficient method of evaluation.

Many computer languages represent polynomials as lists of coefficients, usually starting with the constant term. For example, \(g(x) = -x^5 + 3x^4 +\text{ }2x^2 + x\) would be represented with the list \(\{0,1,2,0,3,-1\}\text{.}\) In both Mathematica and Sage, polynomial expressions can be entered and manipulated, so the list representation is only internal. Some programming languages require users to program polynomial operations with lists. We will leave these programming issues to another source.

Next, we consider a recursive algorithm for a binary search within a sorted list of items. Suppose \(r=\{r(1),r(2), \ldots , r(n)\}\) represent a list of \(n\) items sorted by a numeric key in descending order. The \(j^{th}\) item is denoted \(r(j)\) and its key value by \(r(j).\texttt{key}\text{.}\) For example, each item might contain data on the buildings in a city and the key value might be the height of the building. Then \(r(1)\) would be the item for the tallest building and \(r(1).\texttt{key}\) would be its height. The algorithm \(\texttt{BinarySearch}(j, k)\) can be applied to search for an item in \(r\) with key value \(C\text{.}\) This would be accomplished by the execution of \(\texttt{BinarySearch}(1, n)\text{.}\) When the algorithm is completed, the variable \(\texttt{Found}\) will have a value of \(\texttt{true}\) if an item with the desired key value was found, and the value of \(\textrm{location}\) will be the index of an item whose key is \(C\text{.}\) If \(\texttt{Found}\) keeps the value \(\texttt{false}\text{,}\) no such item exists in the list. The general idea behind the algorithm is illustrated in Figure 8.1.6

In the following implementation of the Binary Search in SageMath, we search within a sorted list of integers. Therefore, the items themselves are the keys.

For the next two examples, consider a sequence of numbers to be a list of numbers consisting of a zeroth number, first number, second number, ... . If a sequence is given the name \(S\text{,}\) the \(k^{th}\) number of \(S\) is usually written \(S_k\) or \(S(k)\text{.}\)

All of the previous examples were presented recursively. That is, every “object” is described in one of two forms. One form is by a simple definition, which is usually called the basis for the recursion. The second form is by a recursive description in which objects are described in terms of themselves, with the following qualification. What is essential for a proper use of recursion is that the objects can be expressed in terms of simpler objects, where “simpler” means closer to the basis of the recursion. To avoid what might be considered a circular definition, the basis must be reached after a finite number of applications of the recursion.

On the other hand, we could compute a term in the Fibonacci sequence such as \(F_5\) by starting with the basis terms and working forward as follows:

This is called an iterative computation of the Fibonacci sequence. Here we start with the basis and work our way forward to a less simple number, such as 5. Try to compute \(F_5\) using the recursive definition for \(F\) as we did for \(F_4\text{.}\) It will take much more time than it would have taken to do the computations above. Iterative computations usually tend to be faster than computations that apply recursion. Therefore, one useful skill is being able to convert a recursive formula into a nonrecursive formula, such as one that requires only iteration or a faster method, if possible.

An iterative formula for \(\binom{n}{k} \) is also much more efficient than an application of the recursive definition. The recursive definition is not without its merits, however. First, the recursive equation is often useful in manipulating algebraic expressions involving binomial coefficients. Second, it gives us an insight into the combinatoric interpretation of \(\binom{n}{k}\text{.}\) In choosing \(k\) elements from \(\{1, 2, . . . , n\}\text{,}\) there are \(\binom{n-1}{k}\) ways of choosing all \(k\) from \(\{1,2, . . . ,n - 1\}\text{,}\) and there are \(\binom{n-1}{k-1}\) ways of choosing the \(k\) elements if \(n\) is to be selected and the remaining \(k - 1\) elements come from \(\{1, 2, . . . , n - 1\}\text{.}\) Note how we used the Law of Addition from Chapter 2 in our reasoning.

BinarySearch Revisited. In the binary search algorithm, the place where recursion is used is easy to pick out. When an item is examined and the key is not the one you want, the search is cut down to a sublist of no more than half the number of items that you were searching in before. Obviously, this is a simpler search. The basis is hidden in the algorithm. The two cases that complete the search can be thought of as the basis. Either you find an item that you want, or the sublist that you have been left to search in is empty, when \(j > k\text{.}\)

BinarySearch can be translated without much difficulty into any language that allows recursive calls to its subprograms. The advantage to such a program is that its coding would be much shorter than a nonrecursive program that does a binary search. However, in most cases the recursive version will be slower and require more memory at execution time.

The definition of the positive integers in terms of Peano’s Postulates is a recursive definition. The basis element is the number 1 and the recursion is that if \(n\) is a positive integer, then so is its successor. In this case, \(n\) is the simple object and the recursion is of a forward type. Of course, the validity of an induction proof is based on our acceptance of this definition. Therefore, the appearance of induction proofs when recursion is used is no coincidence.