Recursive power function: Why does this work if there's no initial return value?

because power(base, exponent) has no return value unless exponent is 0, initially, shouldn't power(base, exponent -1) return 'undefined', and therefore be unmultipliable, initially? So开发者_JS百科, I am having trouble following the logic of this code. Why/how does it work?

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

---

Look at what happens if you try to calculate 5^3:

power(5, 3)  ... this should give us 125, let's see if it does...

function power(base, exponent) {    // base = 5, exponent = 3
  if (exponent == 0)                // nope, exponent != 0
    return 1;
  else
    return base * power(base, exponent - 1);  // return 5 * power(5, 2)
}

... what is power(5, 2) ? ...

function power(base, exponent) {    // base = 5, exponent = 2
  if (exponent == 0)                // nope, exponent != 0
    return 1;
  else
    return base * power(base, exponent - 1);  // return 5 * power(5, 1)
}

... what is power(5, 1) ? ...

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

... what is power(5, 0) ? ...

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

... putting that together, in reverse order as we walk back up the stack...

power(5, 0) = returns 1
power(5, 1) = 5 * power(5, 0) = 5 * 1 =  returns 5
power(5, 2) = 5 * power(5, 1) = 5 * 5 =  returns 25
power(5, 3) = 5 * power(5, 2) = 5 * 25 =  returns 125

... so, power(5, 3) returns 125, as it should.

---

It could be more concise:

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

Howerver an iterative solution is very much faster:

function powerNR(base, exp) {
  var result = 1;
  while(exp--) {
    result *= base;
  }
  return result;
}

---

I think the function makes more sense the other way around, like this:

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

The return of the if statements are chained together and cannot be resolved until the else statement is executed.

Examples

4^0 = else;
4^0 = 1

4^1 = if * else;
4^1 = 4 * 1;

4^2 = if * if * else;
4^2 = 4 * 4 * 1;
    = 4 * 4;
    = 16

// Another way of conceptualising it:

4^2 = if(if(else));
    = 4(4(1));
    = 16;

Remember it is the return of the if/else statements that is being passed back up the chain to the function that called it.

A slightly stupid metaphor

Let's say you want to ask David a question but you don't want to yell, you could ask there person beside you, who could ask the person beside you, who could ask the person beside you, and so on, until the question was asked to David.

const askDavidAQuestion = peopleInBetweenYouAndDavid => {

if (peopleInBetweenYouAndDavid !== 0) {

  console.log('I will ask him');

  return askDavidAQuestion(peopleInBetweenYouAndDavid - 1);

} else {

  console.log('David says no');

}
}

askDavidAQuestion(3);

-> I will ask him
   I will ask him
   I will ask him
   David says no

Only once David's answer is known can that piece of information be passed back up the chain of people that asked the question.

---

A stack of calls to the function is created. This process continues until it meets a termination condition/"base case" - here, a returned value. At that point, all the functions can return and the original function call returns the answer. Explained in other terms, the returned values are popped out of the stack and used to calculate the next step (in inverse order) and so forth until the stack is empty.

Using a 2^2 example:

power(2, 2); calls:

function power(2, 2) {
    if (2 === 0) {
        return 1;
    } else {
        return 2 * power(2, 1); // Called (waits in line to be solved)
    }
}

This leads to:

function power(2, 1) {
    if (1 === 0) {
        return 1;
    } else {
        return 2 * power(2, 0); // Called (waits in line to be solved)
    }
}

This leads to:

function power(2, 0) {
    if (0 === 0) {
        return 1; // Returned (previous calls to recursive case can now be solved)
    } else {
        return 2 * power(2, -1);
    }
}

Now that it has a returned value to work with, it can work back outward, so to speak.

This leads to:

function power(2, 1) {
    if (1 === 0) {
        return 1;
    } else {
        return 2 * 1; // Returned
    }
}

This leads to:

function power(2, 2) {
    if (2 === 0) {
        return 1;
    } else {
        return 2 * 2; // Returned
    }
}

which ultimately returns 4, which is 2^2.

---

All of the listed versions will not work if the exponent is negative. The right version of realization of Math.pow() should be done like this -

    function pow(num1, num2){
        if (num2 === 0){
          return 1;       
        } 
        else if(num2 < 0){
           num2 = Math.abs(num2); 
           return (1 / pow(num1, num2));
        }

        else if(num2 > 0){
           return num1 * (pow(num1,num2 - 1));
        }
};

---

function pow(base, exponent) {
    if (exponent === 0) return 1;
    if (exponent > 0) {
        return base * pow(base, exponent - 1)
    } else {
        // handle negative exponent
        return 1 / base * pow(base, exponent + 1)
    }
}