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

Question

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, 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);
}

Envoy

Um, it returns values in both cases from the if. Can't really see what you're having a problem with. – Underscore

power(13, 5) = 13*(13*(13*(13*(13*power(13, 0))))). The final value is calculated only after the last power() call. The function calculates power(13, 0) which is 1, then 13*1, then 13*(13)... – Muscatel

Oh. You should submit that. That makes sense. – Vinegar

Answer 1

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;
}

Platino

Does : mean else and ? mean 'if it does, return the following'? – Vinegar

The ternary operator is: (test)? <if true return this> : <if false return this> and is equivalent to: if(test){do something}else{do something else}. – Platino

The iterative function is faster because it's only one function call, a recursive function has multiple calls (to itself). Function calls are relatively expensive, avoid them when you can. Recursive functions can be very concise, but that's not necessarily a good reason to use them. They are often difficult to read and slow (but look really cool when you want to do a lot with a little code). – Platino

Awesome. Thanks for keeping me informed, RobG. – Vinegar

Note that these implementations don't handle negative exponents. The example the OP gave doesn't either so I'm not sure it's a big deal, but worth noting for anyone looking to handle both negative and positive exponents. – Carliecarlile

Answer 2

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.

Oddson

Oh. That's what I was thinking, but it was just a hunch. It's much more beautiful when it's written out like this. Thank you. Can I ask what causes it to walk back up, though? – Vinegar

If there's no return value until it hits 0, then it has to go from 0 back up to 3 and receive returns each time, right? Or are there return values on the way down to 0 that add up, which we can list and just 'walk through'? Sorry for the confusion, but I don't really know if 'walk' means the program is running the numbers, or if it means that people can look at them because they exist. Is it a technical term or something? – Vinegar

Ah, I see. Because it's undefined, it's just multiplying 13*undefined*13 (which turns out as 13*13), and then finally multiplying the result by 1 and ending the program because of the return. So, walking through means mentally, I guess. Cool. – Vinegar

Answer 3

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.

Batch

Answer 4

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.

Verify

Answer 5

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));
        }
};

Worthwhile

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Exuviae

Answer 6

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)
    }
}

Etti