16.3 A Simple Recursive Function

The exponentiation operation, yⁿ, is an example of a function that can be defined recursively. The general, informal description of exponentiation is:

yⁿ = y y y y ... y

For example,

y³ = y y y

16.3.1 Mathematical Specification of Exponentiation

A mathematical specification of the exponentiation function that is recursive is as follows, assuming that n ≥ 0:

The base case in this recursive definition is the value of 1 for the function if the argument has value zero, that is yⁿ = 1 for n = 0. The recursive case is yⁿ = y yⁿ^-1, if the value of the argument is greater than zero.

16.3.2 Evaluating Exponentiation

To facilitate the handling of the exponentiation function, it is named expon with two arguments: the base and the power. For example, yⁿ is denoted as expon(y, n).

For evaluating the function 2⁴, which is denoted as expon(2,4), Table 16.1 shows all the intermediate calculations necessary.

Table 16.1: Intermediate calculations for 2⁴
2⁴	2 2³	2 expon(2, 3)
2³	2 2²	2 expon(2, 2)
2²	2 2¹	2 expon(2, 1)
2¹	2 2⁰	2 expon(2, 0)
2⁰	1	1

16.3.3 KJP Implementation of Exponentiation

The following function is a recursive solution for the exponentiation function, expon(y, n). The KJP code defines a static function that is called by function main in class Rectest.

       description          This function computes recursively y to the          power of n, assuming that n > 0. */       static function expon of type double                    parameters double y, integer n is         variables           double result         begin         display "expon ", y, " power ", n         // base case         if n == 0 then            set result = 1.0         else            // recursive case            if n greater than 0 then               set result = y * expon(y, n-1)               display "y = ", y, " n = ", n,                                   " expon ", result            else               // exceptional case               display "Negative power"               set result = 1.0            endif         endif         return result       endfun expon

On the CD

The KJP code that implements class Rectest is stored in the file Rectest.kpl. The Java implementation is stored in the file Rectest.java.

When the program implemented in class Rectest executes, with a value 3.0 for y and value 4 for n, the intermediate and final results are shown as follows:

            ----jGRASP exec: java Rectest           Enter value for n:           4           type value for y:           3.0           expon 3.0 power 4           expon 3.0 power 3           expon 3.0 power 2           expon 3.0 power 1           expon 3.0 power 0           y = 3.0 n = 1 expon 3.0           y = 3.0 n = 2 expon 9.0           y = 3.0 n = 3 expon 27.0           y = 3.0 n = 4 expon 81.0           Expon 3.0 power 4 is 81.0            ----jGRASP: operation complete.

When analyzing the intermediate results for the computation of the recursive function expon, it is clear those successive calls to the function continue until it reaches the base case. After this simple calculation of the base, the function starts calculating the exponentiation of y with power 1, 2, 3, and then 4. There are actually two phases in the calculation using a recursive function:

The recursive calls up to the base case. This represents the sequence of calls to the function; it is known as the winding phase.
The unwinding phase returns the values from the base case to each of the previous calls.