# a to the power of b – recursive algorithm

• A+
Category：Languages

I am having a hard time understanding the following recursive algorithm in terms of the multiplication operation used in the code.

``int power(int a, int b) {     if (b < 0) {         return 0;     } else if (b == 0) {         return 1;     } else {                    return a * power(a, b - 1);     } } ``

For inputs (3,7) the result would be 2187. There are total of 6 recursive calls being made:

``Initial values - 3,7 First recursive call(3,6) Second recursive call(3,5) Third recursive call(3,4) Fourth recursive call(3,3) Fifth recursive call(3,2) Sixth recursive call(3,1) ``

Given the following formula:

``a * power(a, b - 1) ``

is each recursive call multiplying the values of a & b? Which wouldn't make sense, since that would return 81 at the end. I am trying to understand the factors and product in the multiplication operation of each recursive call.

You have to keep in mind that `a` is multiplied by the result of the recursive function call at every step. You might look at it like this:

``power(3,7) = 3 * power(3,6) = 3 * 3 * power(3,5) = 3 * 3 * 3 * power(3,4) = 3 * 3 * 3 * 3 * power(3,3) = 3 * 3 * 3 * 3 * 3 * power(3,2) = 3 * 3 * 3 * 3 * 3 * 3 * power(3,1) = 3 * 3 * 3 * 3 * 3 * 3 * 3 * power(3,0) = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 1 // by definition when b = 0 ``

At each step we replace the call to `power(a,b)` with `a * power(a,b-1)`, as the function defines, until we get to `power(3,0)`. Does that help clear up what's going on?