javascript - 堆栈和递归函数

Question

我希望这不是一个重复的问题——尽管我在这方面找不到太多帮助。

我正在练习递归函数(我是新手)，我正在尝试将数组中的每个数字相乘。有点像阶乘。我有这段代码，但它只返回 undefined 作为结果。

代码如下:

 var stack = [];

function countDown(int) {
  stack.push(int);
  if (int === 1) {  
    return 1;
  }
    return countDown(int - 1);
}

function multiplyEach() {
  // Remove the last value of the stack 
  // and assign it to the variable int
  int = stack.pop();
  x = stack.length;
  // Base case
  if ( x === 0 ) {
    return;
  }
  // Recursive case
  else {
    stack[int - 1] = int * stack[x - 1];
    return multiplyEach(int);
  }
}

// Call the function countDown(7)
countDown(7);
// And then print out the value returned by multiplyEach()
console.log(multiplyEach());

非常感谢您提供任何见解。

干杯!

Answer 1

首先要解决的问题是，从外观上看，您的 multiplyEach() 函数应该有一个名为 int 的参数。您使用的方法可能更适合不同的技术，但我们会谈到这一点。

接下来，在multiplyEach()中，有两种可能的路径:

1. 堆栈仍然有元素，在这种情况下，我们将堆栈中的新顶部值乘以旧值，然后继续运行另一次 multiplyEach。

2. 栈是空的，我们就返回。

这里的问题是我们实际上并没有返回最终的堆栈值，或者将它留在那里供以后访问。我们实际上已经丢失了它，那么函数输出的是什么？

在许多语言中，我们会为这个函数定义一个返回类型，void 表示没有值，或者 int 表示返回相乘后的值。但是，在 Javascript 中，不存在不返回值的函数； JS 中的“无”表示为 undefined。当您返回 multiplyEach() 时，您将对它的另一个调用插入调用堆栈，并等待实际的返回值...最终是 return;，JS 将其解释为 返回未定义；。同样，在大多数语言中，都会有某种形式的错误，但在 JS 中不会!让我们看一下两种可能的实现方式:

1. 您使用的自定义堆栈:

   // your stack is fine, so we'll skip to the meat
   function multiplyEach() {
       var int = stack.pop(), x = stack.length;
       stack[x - 1] *= int;
       if(x < 2) // to multiply, we need at least two numbers left
           return;
       multiplyEach();
   }
   
   //...
   multiplyEach();
   console.log(stack[0]);
   

2. 使用一个参数，并使用一个列表:

   function multiplyEach(index) {
       var int = list[index];
       if(index == 0)
           return int;
       return int * multiplyEach(index - 1);
   }
   
   //...
   console.log(multiplyEach(list.length - 1));
   

它们都是递归实现的不同方式；所有递归本质上要求的是函数调用自身。另一种可能性是让参数存储总数，而不是像选项 2 那样乘以返回值；这就是所谓的尾递归。

编辑:注意到选项 1 的基本情况在错误的位置，所以我移动了它。它现在应该可以工作了。