In fact, we can write the formula most concisely as
This definition of XN is a classic recursive definitionthat is, a definition given in terms of a smaller version of itself.
Recursive Definition A definition in which something is defined in terms of smaller versions of itself.
XN is defined in terms of multiplying X times XN-1. How is XN-1 defined? Why, as X * XN-2, of course! And XN-2 is X * XN-3;XN-3 is X * XN-4; and so on. In this example, in terms of smaller versions of itself means that the exponent is decremented each time.
When does the process stop? When we have reached a case where we know the answer without resorting to a recursive definition. In this example, it is the case where N equals 1: X1 is X. The case (or cases) for which an answer is explicitly known is called the base case. The case for which the solution is expressed in terms of a smaller version of itself is called the recursive or general case. A recursive algorithm is an algorithm that expresses the solution in terms of a call to itself, a recursive call. A recursive algorithm must terminate; that is, it must have a base case.
Base Case The case for which the solution can be stated nonrecursively.
General Case The case for which the solution is expressed in terms of a smaller version of itself; also known as recursive case.
Recursive Algorithm A solution that is expressed in terms of (a) smaller instances of itself and (b) a base case.
Figure 19-1 shows a recursive version of the Power function with the base case and the recursive call marked. The function is embedded in a program that reads in a number and an exponent and prints the result.
