- A+

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?