Confusion In Eloquent Javascript Power Recursion Sample

this recursion code is from the book of eloquent javascript function power(base, exponent) { if (exponent == 0) { return 1; } else { return base * power(base, exponen

Solution 1:

But how did base got multiplied by exponent

It doesn't multiply by the exponent.

The exponent is being used as a counter to end the recursive cycle once it's been reduced to 0. The base is instead being multiplied by itself an exponent number of times.

This is supported by each call to power() returning either 1 or the value of base. In the latter case, power() is called again to get 1 or another copy of base to multiply by. And, this repeats until it does finally return 1 as the final multiplier.

power(2, 3) ==
        2 * power(2, 2) == // base * ...2 * 2 * power(2, 1) == // base * (base * ...)2 * 2 * 2 * power(2, 0) == // base * (base * (base * ...))2 * 2 * 2 * 1// base * (base * (base * (1)))

---

The same steps could also be defined with a loop, though using 1 as the initial value rather then at the end:

function power(base, exponent) {
    var result = 1;

    while (exponent) {
        result *= base;
        exponent--;
    }

    return result;
}

console.log(power(2, 3)); // 1 * base * base * base == 1 * 2 * 2 * 2 == 8

Solution 2:

I find it easy to understand recursive procedures by looking at their base case first, then building up from there – here's the function we're studying...

function power(base, exponent) {
  if (exponent == 0) {
    return1;
  }
  else {
    returnbase * power(base, exponent - 1);
  }
}

So here, the base case is exponent == 0. We'll keep 2 as the input for base:

power(2, 0) => 1

Well that was really easy! All we had to do was evaluate an if statement and we arrived at our answer. Looking ahead, we see that power arrives at its base case by subtracting 1 from the exponent (exponent - 1), we'll reverse this to get our next input – so instead of power(2, 0) we will do power(2, 1)

power(2, 1) => 2 * power(2, 0)
            => but wait! don't re-evaluate power(2,0)! we already know that answer from above
            => 2 * 1
            => 2

Ok, we'll keep doing the same thing by incrementing exponent by 1 each time. But be careful not to do unnecessary work – if we've already evaluated one of the expressions earlier, just replace that expression with it's evaluated value

power(2,2) => 2 * power(2, 1)
           => we already know power(2,1) == 2 ...
           => 2 * 2
           => 4

power(2,3) => 2 * power(2,2)
           => we already know power(2,2) == 4, etc
           => 2 * 4
           => 8

power(2,4) => 2 * power(2,3)
           => 2 * 8
           => 16

power(2,5) => 2 * power(2,4)
           => 2 * 16
           => 32

Now we can easily see a pattern and how the recursive procedure works in general

Solution 3:

What you have to notice is that the power function returns 1 when exponent is 0 and return base * power() on another case.

Pay attention to power function

In the following code

power(base, exponent - 1);

you have to appreciate some things

1) If exponent is 1 the function power returns 1 so in here

returnbase * power(base, exponent - 1);

Whether base is 2

return2 * 1

The function power is returning 2, so in the next step

returnbase * power(base, exponent - 1);

means

return2 * 2;

which is 4, that means that function power is returning 4

I think you can catch up from here.

Let me know if you understood :)