递归幂函数：如果没有初始返回值，为什么它会起作用？

Question

因为除非指数为 0，否则 power(base, exponent) 没有返回值，所以最初 power(base, exponent -1) 不应该返回“未定义”，因此最初是不可乘的吗？所以，我在遵循这段代码的逻辑时遇到了困难。为什么/如何运作？

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

Answer 1

看看如果您尝试计算 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)
}

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

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

...什么是 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);
}

...当我们沿着堆栈向上走时，以相反的顺序将它们放在一起...

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.

Answer 2

它可以更简洁：

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

然而，迭代解决方案要快得多：

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

Answer 3

我认为该函数反过来更有意义，如下所示：

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

if 语句的 return 链接在一起，直到 else 语句< /em> 被执行。

示例

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;

记住它是 if/else 语句的返回，它沿着链向上传递到调用它的函数。

一个有点愚蠢的比喻

假设你想问大卫一个问题，但你又不想大喊大叫，你可以问你旁边的人，谁可以问你旁边的人，谁可以问那个人在你旁边，依此类推，直到这个问题被问到大卫。

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

只有知道大卫的答案后，这条信息才能被传回到提出问题的人链上。

Answer 4

创建对该函数的调用堆栈。此过程持续进行，直到满足终止条件/“基本情况” - 此处为返回值。此时，所有函数都可以返回，并且原始函数调用将返回答案。换句话说，返回的值将从堆栈中弹出并用于计算下一步（按相反顺序），依此类推，直到堆栈为空。

使用 2^2 示例：

power(2, 2);
调用：

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

这导致：

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

​​ 这导致：

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

​​ 现在它有一个可以使用的返回值，可以这么说，它可以向外工作。

这导致：

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

这导致：

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

​​ 最终返回 4，即 2^2。

Answer 5

如果指数为负数，所有列出的版本都将不起作用。 Math.pow() 的正确实现版本应该像这样完成 -

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

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