To program the mathematical function b^e, where b and e are non-negative integers, a recursive method can be written and used. Assume an existing method sqr(int a) that returns an integer, that is the square of int a.
public static int exp(int b, int e)
{
if(e == 0)
return 1;
else if (e%2 == 0)
return sqr(exp(b,e/2));
else
return b*exp(b,e-1);
}
This program takes advantage of the property that (a^b)^c = a^(b*c). For example, 3^16 = (3^8)^2. Therefore, if the exponent e is even, the next call uses e/2 while the entire result is simply squared. The advantage then is that this program runs in O(log e) efficiency, rather than the O(e) efficiency, had the boolean test of e being even not been tested.
To illustrate the running of the program using memory stacks, illustrated up-side-down, here's a case of an even exponential. For example, to calculate 3^4, or running of exp(3,4):
- return exp(3,4)
- return sqr(exp(3,2))
- return sqr(exp(3,1))
- return 3*exp(3,0)
To see what each memory stack returns to the previous, follow each from the bottom of the list back up:
- 3*exp(3,0) --> 3 --> exp(3,1)
- sqr(exp(3,1)) --> 9 --> exp(3,2)
- sqr(exp(3,2)) --> 81 --> exp(3,4)
- return exp(3,4) //equals 81
Indeed, 3^4 = 81 as returned. Note that exp(3,3) was never called, since during exp(3,4), as 4 is an even integer, it directly halved the exponential called next, and moved onto exp(3,2). While a linear efficiency only would've meant an extra step in this scenario, the difference will be more pronounced when the exponential gets substantially bigger. Consider exp(3,80): instead of 81 calls, this logarithmically efficient method would only have to call exp(3,80), exp(3,40), exp(3,20), exp(3,10), exp(3,5), exp(3,4), exp(3,2), exp(3,1), exp(3,0) for a total of 9 calls.
