Need help understanding recursive function example from Eloquent 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 1

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.

Answer 2

Follow the call pattern.. Let's assume we do power(2,2).. You get this:

power(2,2) -> (exponent != 0) 2 * power(2, 1)

2 * power(2, 1) -> (exponent != 0) 2 * power(2, 0)

2 * 2 * power(2,0) -> (exponent == 0) 1

2 * 2 * 1 = 4

The way it works is basically your call stack, as long as you keep calling sub-methods, your parent doesn't return. So it keeps nesting itself until it hits a concrete # -- in this case, 1, then it goes back up the stack actually doing the *.

Answer 3

This shows intermediate results which may help you to follow the logic:
Each level has its own value of base, exponent, answer.

function power(base, exponent) {
  var answer; // local
  level = level + 1;
  console.log("Entering: power(" + base + ", " + exponent + 
      ") (level " + level + ")");
  if (exponent == 0) { // don't recurse any more
    answer = 1; }
  else {               // recurse to get answer
    answer = base * power(base, exponent - 1); }
  // now return answer
  console.log("Leaving: power("+ base + ", " + exponent + 
      ") (level " + level + ") ans=" + answer);
  level = level - 1
  return answer;
  }
var level = 0; // global
console.log("Final answer: " + power(2, 5)); 

Answer 4

The best way to explain the above recursive is to see what the console returns

 function power(base, exponent) {
     // termination/base case
     if (exponent == 0)
        return 1;
     // recursive case
     else
        console.log(base + ':' + exponent)
        return base * power(base, exponent - 1);

     //  2 * (2, 4) = 4
     //  4 * (2, 3) = 8
     //  8 * (2, 2) = 16
     //  16 *(2, 1) = 32
     //  16 *(2, 0) = 1 recursive stops and returns 1
     //  function calls the last return  = 32

  } 

  var result = power(2,10)
  console.log(result)

I hope this give you a more visual view of how this recursive works

Answer 5

This also confused heck out of me when i first saw it, after 10 minutes starring at it, it just came to me....nothing magical....

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

console.log(power(2, 5));

this is how it runs through:

return base * power(base, exponent - 1)

looking at the above line itself, I was lost too. there are no operations(+,-,*,/,%) done to the given parameters 2 and 5, but somehow at the end, console.log just know to produce correct number.

Because it does not return a numeric value, it simply returns base * power(base, exponent -1) itself, when program reaches power(base, exponent -1), it executes it before return happens, until exponent == 0 becomes true.

1st: return base * power(base, 5 - 1);

2nd: return base * base * power(base, 4 - 1);

3rd: return base * base * base * power(base, 3 - 1);

4th: return base * base * base * base * power(base, 2 - 1);

5th: return base * base * base * base * base * power(base, 1 - 1);

6th: return base * base * base * base * base * 1;

because if (exponent == 0) return 1

so: 2*2*2*2*2*1 = 32