user3376521 - 1 year ago 63

Javascript Question

`function power(base, exponent) {`

if (exponent == 0)

return 1;

else

return base * power(base, exponent - 1);

}

I think that I understand the basic principle of recursion, it simply means you are calling the function within the function itself. This can be used to perform a loop of sorts, but what I cant figure out is how the above code actually decides to loop in order to figure out the exponential value of a number. I used function power(2,5) as my argument and the function knew the answer was 32, but how? Does the function loop itself subtracting 1 from the exponent each time, and multiplying base * base until exponent reaches zero? And if thats the case, how does calling the power function within the function accomplish this exactly? And once exponent reaches zero, wouldnt the function then just return 1 and not the correct answer?

Answer Source

I consider each recursive step (the function calling itself) producing a shorter and easier problem.

The easiest problem is power(base, 0), which satisfies `exponent == 0`

and returns one (any base to the zeroth power is 1).

Then, notice that no matter how large exponent is, it is reducing `exponent`

by one, guaranteeing that it will eventually reach the "easiest" problem where the exponent is zero. It only can't be negative, or else this "base case" is never reached.

So, 2^5, or power(2, 5), becomes 2 * 2^4. And 2^4 = 2 * 2^3. By continuing this expansion, we get 2 * 2 * 2 * 2 * 2 * 1, which equals 32. The `1`

represents the case `exponent == 0`

being true.

The computation has to keep track how many of these multiplications it has accumulated, and once the base case of `exponent == 0`

is reached, multiply all numbers together. It cannot know in advance with certainty what `power(base, exponent-1)`

will return.