|
|
|
|
|
|
|
FIGURE 19-1 Power Function |
|
|
|
|
|
|
|
|
//******************************************************************
// Exponentiation program
//******************************************************************
#include <iostream.h>
int Power( int, int );
int main()
{
int number; // Number that is being raised to power
int exponent; // Power the number is being raised to
cin >> number >> exponent;
cout << Power(number, exponent); ¼ // Nonrecursive call
return 0;
}
//******************************************************************
int Power( /* in */ int x, // Number that is being raised to power
/* in */ int n ) // Power the number is being raised to
// Computes x to the n power by multiplying x times the result of
// computing x to the n - 1 power.
// Precondition:
// x is assigned && n > 0
// Postcondition:
// Function value == x raised to the power n
// Note:
// Large exponents may result in integer overflow
{
if (n == 1)
return x; ¼ // Base case
else
return x * Power (x, n - 1); ¼ // Recursive call
} |
|
|
|
|
|
|
|
|
Each recursive call to Power can be thought of as creating a completely new copy of the function, each with its own copies of the parameters x and n. The value of x remains the same for each version of Power, but the value of n decreases by one for each call until it becomes 1. |
|
|
|
|
|
|
|
|
Let's trace the execution of this recursive function, with number equal to 2 and exponent equal to 3. We use a new format to trace recursive routines: we number the calls and then discuss what is happening in paragraph form. |
|
|
|
|
|
|
|
|
Call 1: Power is called by main, with number equal to 2 and exponent equal to 3. Within Power, the formal parameters x and n are initialized to 2 and 3, respectively. Because n is not equal to 1, Power is called recursively with x |
|
|
|
|
|