Section 8.1 The Many Faces of Recursion
Consider the following definitions, all of which should be somewhat familiar to you. When reading them, concentrate on how they are similar.
Subsection 8.1.1 Binomial Coefficients
Here is a recursive definition of binomial coefficients, which we introduced in Chapter 2.
Observation 8.1.2.
A word about definitions: Strictly speaking, when mathematical objects such as binomial coefficients are defined, they should be defined just once. Since we defined binomial coefficients earlier, in Definition 2.4.3, other statements describing them should be theorems. The theorem, in this case, would be that the “definition” above is consistent with the original definition. Our point in this chapter in discussing recursion is to observe alternative definitions that have a recursive nature. In the exercises, you will have the opportunity to prove that the two definitions are indeed equivalent.
Subsection 8.1.2 Polynomials and Their Evaluation
Definition 8.1.3. Polynomial Expression in over (Non-Recursive).
Let be an integer, An degree polynomial in is an expression of the form where are elements of some designated set of numbers, called the set of coefficients and
We refer to as a variable here, although the more precise term for 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.
This definition is often introduced in algebra courses to describe expressions such as a third-degree, or cubic, polynomial in This definition has a drawback when the variable is given a value and the expression must be evaluated. For example, suppose that Your first impulse is likely to do this:
A count of the number of operations performed shows that five multiplications and three additions/subtractions were performed. The first two multiplications compute and and the last three multiply the powers of 7 times the coefficients. This gives you the four terms; and adding/subtracting a list of numbers requires addition/subtractions. The following definition of a polynomial expression suggests another more efficient method of evaluation.
Definition 8.1.4. Polynomial Expression in over (Recursive).
-
For
an degree polynomial expression in over is an expression of the form where is an degree polynomial expression in and
We can easily verify that is a third-degree polynomial expression in over based on this definition:
Notice that 4 is a zeroth degree polynomial since it is an integer. Therefore is a first-degree polynomial; therefore, is a second-degree polynomial in over therefore, is a third-degree polynomial in over The final expression for is called its telescoping form. If we use it to calculate we need only three multiplications and three additions/subtractions. This is called Horner’s method for evaluating a polynomial expression.
Example 8.1.5. More Telescoping Polynomials.
-
The telescoping form of
is Using Horner’s method, computing the value of requires four multiplications and four additions/subtractions for any real number
Many computer languages represent polynomials as lists of coefficients, usually starting with the constant term. For example, would be represented with the list 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.
Subsection 8.1.3 Recursive Searching - The Binary Search
Next, we consider a recursive algorithm for a binary search within a sorted list of items. Suppose represent a list of items sorted by a numeric key in descending order. The item is denoted and its key value by 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 would be the item for the tallest building and would be its height. The algorithm can be applied to search for an item in with key value This would be accomplished by the execution of When the algorithm is completed, the variable will have a value of if an item with the desired key value was found, and the value of will be the index of an item whose key is If keeps the value no such item exists in the list. The general idea behind the algorithm is illustrated in Figure 8.1.6

General Scheme for a Binary Search.
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.
xxxxxxxxxx
def BinarySearch(r,j,k,C):
found = False
if j <= k:
mid = floor((j + k)/2)
print('probing at position '+str(mid))
if r[mid] == C:
location = mid
found = True
print('found in position '+str(location))
return location
else:
if r[mid] > C:
BinarySearch(r,j, mid - 1,C)
else:
BinarySearch(r,mid + 1,k,C)
else:
print('not found')
return False
s=[1,9,13,16,30,31,32,33,36,37,38,45,49,50,52,61,63,64,69,77,79,80,81,83,86,90,93,96]
BinarySearch(s,0,len(s)-1,30)
Subsection 8.1.4 Recursively Defined Sequences
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 the number of is usually written or
Example 8.1.7. Geometric Growth Sequence.
These rules stipulate that each number in the list is 1.08 times the previous number, with the starting number equal to 100. For example
Subsection 8.1.5 Recursion
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.
To determine, for example, the fourth item in the Fibonacci sequence we repeatedly apply the recursive rule for until we are left with an expression involving and
Subsection 8.1.6 Iteration
On the other hand, we could compute a term in the Fibonacci sequence such as 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 using the recursive definition for as we did for 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 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 In choosing elements from there are ways of choosing all from and there are ways of choosing the elements if is to be selected and the remaining elements come from 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
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.
Subsection 8.1.7 Induction and Recursion
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 is a positive integer, then so is its successor. In this case, 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.
Example 8.1.10. Proof of a formula for .
If then as defined. Now assume that for some the formula for is true.
hence the formula is true for
The formula that we have just proven for is called a closed form expression. It involves no recursion or summation signs.
Definition 8.1.11. Closed Form Expression.
Let be an algebraic expression involving variables which are allowed to take on values from some predetermined set. is a closed form expression if there exists a number such that the evaluation of with any allowed values of the variables will take no more than operations (alternatively, time units).
Example 8.1.12. Reducing a summation to closed form.
The sum is not a closed form expression because the number of additions needed to evaluate grows indefinitely with A closed form expression that computes the value of is which only requires operations.
Exercises 8.1.8 Exercises
1.
By the recursive definition of binomial coefficients, Continue expanding to express it in terms of quantities defined by the basis. Check your result by applying the factorial definition of
2.
3.
Let
-
Write
in telescoping form. -
Compare your speed in parts b and c.
4.
Suppose that a list of nine items, is sorted by key in decending order so that and List the executions of the BinarySearch algorithms that would be needed to complete BinarySearch(1,9) when:
-
The search key is C = 12
-
The search key is C = 11
Assume that distinct items have distinct keys.
5.
6.
Prove the two definitions of binomials coefficients, Definition 2.4.3 and Definition 8.1.1, are equivalent.
7.
You have attempted 1 of 1 activities on this page.