理解递归后的执行 - 递归如何确定何时停止？

Question

我知道这里有许多递归线程。从技术上讲，我确实理解递归背后的原理，我只是对存储实际递归计数器的位置或者编译器如何跟踪它更加好奇

代码可能更好地理解这一点。我在javascript中创建了一个简单的递归函数。

function factorial(number){
    if (number > 1) {
    return number * factorial(number - 1);
  } else {
    return number;
  }
}

现在，每个人都明白这是如何运作的。我们在factorial上调用递归函数，递归重复直到函数结束。

我的问题是，为什么阶乘函数会在正确的时间停止执行递归？如果我们试图在我们的脑海中调试函数，我的理解是，它看起来像这样：

假设我们打电话给factorial(3);

1. 调用的函数 - >加载参数
2. 计算IF条件 - > 3> 1 - >应用递归函数
3. 3 *递归（2）*递归（1）=> 3 * 2 * 1 = 6

现在我的问题是，这怎么可能？ a）如果我们将递归计数器减少到1，我们没有输入else {语句，因为它应该被评估为false，而b）递归计数器怎么知道，循环递归函数只有数量-Nth of amount次？

为了更好地说明，我添加了以下代码行document.write("entered with number " + number + "</br>");，因此我们将在每次输入if条件时将其打印出来。

function factorial(number){
	if (number > 1) {
  	document.write("entered with number " + number + "</br>");
  	return number * factorial(number - 1);
  } else {
  	return number;
  }
}

document.write(factorial(3) + "<br/>");

正如你所看到的，if条件如果条件被评估为真并且打印出3和2的消息。为什么计数器没有循环低，如果我们在else { return number; }上调用递归操作，我们怎么也不会返回到初始的factorial(2-1) ？

这是一个相当困难的问题，所以如果您对如何更好地表达它有任何想法，请随时编辑我的问题！

Answer 1

这里有一个关于递归正在做什么的口头描述，太详细了：

1. 你在factorial(3)中打电话给document.write()。
2. factorial(3)想要返回3 * factorial(2)。在它返回一个值之前，它必须弄清楚factorial(2)的意思。
3. 所以现在我们有factorial(3)等待factorial(2)的结果。 factorial(2)运行，并希望返回2 * factorial(1)。在它返回一个值之前，它必须解决factorial(1)的含义。
4. 现在我们有factorial(3)等待factorial(2)的结果，等待factorial(1)的结果。 factorial(1)运行，并且看到它的输入是1，所以命中“else”块，所以只返回1给它的调用者factorial(2)。
5. 现在factorial(2)有它需要的东西，所以可以将2 * 1返回给它的来电者factorial(3)。
6. 现在factorial(3)有它需要的东西，所以可以将3 * 2返回给它的来电者。
7. 呼叫document.write收到“6”。

递归“知道”停止的位置，因为它最终会到达一个只返回数字1的点，而不是返回依赖于对factorial()的另一个调用的东西。如果函数总是试图调用自己，那么就没有办法摆脱递归循环;它会一直持续到堆栈溢出。

除了factorial(1)之外，每次调用factorial(n)最终都会调用factorial(n-1) - 所以请注意factorial(0)或factorial(-1)或factorial(1.01)永远不会达到1，所以递归将继续运行直到堆栈溢出。在编写递归函数时，最好注意并处理永远不会到达出口点的输入;在这种情况下，如果输入不是正整数，则您想要抛出错误。

为什么计数器没有循环降低，为什么我们永远不会回到最初的其他地方{返回号码;如果我们在factorial（2-1）上调用递归操作？

它确实如此，但你在函数内的document.write在if块内部，所以当函数进入else块时没有打印出来。这是相同功能的更详细版本，可以让您更清楚地了解发生的情况：

function factorial(number) {
  document.write("entered with number " + number + "<br>");
  if (number > 1) {
    document.write("recursing<br>")
    return number * factorial(number - 1);
  } else {
    document.write("Returning 1<br>")
    return number;
  }
}

document.write(factorial(3) + "<br>");

什么确切地决定了递归何时停止？当函数的递归返回相同的结果两次（在这种情况下为1？）或是否有一些不同的触发器？

尽量不要考虑到某种类型的“计数器”来跟踪函数何时应该停止递归，或者是一个主动阻止它的“触发器” - 这是一种误导性的方式来看待它。函数的每个实例只知道它接收的输入以及它想要返回的内容。它大多数时候想要返回的内容恰好包括对同一函数的调用，这就是递归的来源;当它想要返回的内容不涉及函数调用时，递归就结束了。

对于此特定函数，对于除1之外的任何输入，它将使用输入n-1调用其自身的新实例（并在它返回其父调用者之前等待结果），因此递归继续。对于1的输入，它不会调用自身，因此递归结束。那个'else'块是你的“触发器”（但是，再一次，这是一种误导性的思考方式;它不是“触发”任何东西，它只是返回一个数字而不是调用一个函数来返回它的结果。）

f(3)称f(2)称f(1)不叫任何东西。如果你编辑函数用n+1而不是n-1来调用自己，那么f(3)会调用f(4)来调用f(5)，依此类推，直到你的内存耗尽为止。