TABLE OF CONTENTS In this chapter we examine how recursion is used to implement algorithms in computer algebra. We begin, in Section 5.1, by describing how a simple recursive procedure is implemented by a CAS. In Section 5.2, we give recursive procedures for a number of operators and describe an approach using transformation rules that provides a simple way to implement some recursive operations. Finally, in Section 5.3 we describe a recursive algorithm for a simple version of the Integral operator that utilizes some basic integration rules together with the substitution method.
In Chapter 3 we gave the following recursive definition for the factorial operation:
For n=4, the computation based on this definition (5.1) proceeds as follows:
To perform the calculation, we repeatedly apply (5.1) until n=0 is encountered. Once this point is reached, 0! is replaced by the value 1, and the numerical computation proceeds as indicated by the parentheses in the second line of Equations (5.2).
Figure 5.1 shows an MPL recursive procedure that performs this calculation. For the case n>0, the procedure calls on itself (line 4) to perform a simpler version of the calculation. A procedure that calls on itself directly (as in this example) or indirectly through a sequence of procedures is called a recursive procedure. The case n=0 (lines 1, 2) is called a ter mination condition for the procedure, since it is defined directly and does not require further calls on Rec_fact.
