Section 1 - Recursive Functions

9B.1.1 Recursion

We will introduce a new functional concept: recursion.

Look at this example:

#include <cmath>
#include <iostream>
using namespace std;

// function prototypes -----------------------
double myPow(double base, long exp);

int main()
{
cout << myPow(2.4, 4) << " vs. " << pow(2.4, 4) << endl;
cout << myPow(1.23, 9) << " vs. " << pow(1.23, 9) << endl;
cout << myPow(5535, -29) << " vs. " << pow(5535., -29) << endl;
}

// -------  My Power --------------
double myPow(double base, long exp)
{
if (exp == 0)
return 1.;
if (exp < 0)
return 1. / myPow( base, -exp);
else
return base * myPow( base, exp-1 );
}

As you see, I am defining my own home-rolled version of the <cmath> function pow() which I call myPow().  In my version, I only care about integer exponents, so I make the exponent parameter a long.  Then, I test to see if I get the same results as <cmath> pow(), and, of course, I do.  The odd thing about this method is that it calls itself!

Recursion is sometimes defined as a method calling itself, and myPow() certainly does that. There is more to it than that, but that usually gets the right neurons firing when thinking about the concept.

This method myPow() used to compute a base to an exp power, say 2.4⁴ or "2.4 raised to the 4th power" which is

2.4 * 2.4 * 2.4 * 2.4

The way this method works is by breaking the situation into cases. Ignore the exp<0 case for now.

• If exp == 0, then the answer is 1, because ANYTHING TO THE ZERO POWER IS 1. If you didn't know that before, now you do.
   
• If exp is  > 0, Let's say 4, then myPow(base, 4) ends up using the final else statement of the method, which will evaluate to:

base * myPow(base, 3);

So the function calls itself using the same base, but a power of 3, instead of 4. Whatever answer the function gets on that "inner" call, it multiplies by the base, 4, and that is the answer we want. This should make sense to you, since

base⁴ is nothing more than base * base³

In fact, this always works: myPow(7, 5) is computed by finding myPow(7, 4) and multiplying that answer by one more 7. You don't have to follow the logic all the way down, just realize that if the function keeps calling itself, as it will do, the exp gets smaller and smaller until it finally hits 0, at which time, the function returns a 1. Then the function calls which have built up, start "paying off" or "unwinding" resulting in that 1 being multiplied by a 7, that answer being multiplied by another 7, etc. 5 times. It sounds messy, but look at the program. It's really clean and simple.

• The exp < 0 case is for negative exponents. A negative exponent is just the reciprocal of the positive exponent (remember that high school arithmetic?) so that is why that case looks as it does.

In general, a recursive function has at least two cases.

• One case returns a value without the function calling itself.  There is no recursive call in this case.  This is called the escape case.
• The other case(s) results in the function calling itself, but the inner function call uses different arguments than the function itself was passed.  The new arguments that it passes to "itself" must bring us closer to the so-called escape case (above).

In our example, the escape case is when exp==0.  And the other cases always result in a recursive call that brings us closer to that escape case because, for example, if we enter the method with exp equal to7, then we call myPow() recursively passing in 6 to the exp, thus bringing it closer to the escape case of 0.

As you can see, the above program works:

33.1776 vs. 33.1776
6.44386 vs. 6.44386
2.81572e-109 vs. 2.81572e-109
Press any key to continue . . .