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?

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: