了解递归背后的执行——递归如何确定何时停止？

Question

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

这可能通过代码更容易理解。我在 javascript.

中创建了一个简单的递归函数

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

现在，每个人都明白这是怎么回事了。我们在阶乘上调用递归函数，递归地重复直到函数结束。

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

假设我们调用了 factorial(3);

Function Invoked -> Load Arguments

Calculcate the IF condition -> 3 > 1 -> apply recursive function

3 * recursive(2) * recursive(1) => 3 * 2 * 1 = 6

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

为了更好地说明，我添加了以下代码行 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 条件 if 条件评估为 true 并打印出 3 和 2 的消息。为什么计数器没有循环降低，为什么我们从未返回到initial else { return number; } 如果我们在 factorial(2-1)?

上调用递归操作

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

Answer 1

这里是对递归正在做什么的口头描述，太详细了：

您在 document.write() 中调用 factorial(3)。
factorial(3)想return3 * factorial(2)。在它可以 return 一个值之前，它必须弄清楚 factorial(2) 是什么意思。
现在我们有 factorial(3) 等待 factorial(2) 的结果。 factorial(2)运行s，想return2 * factorial(1)。在它可以 return 一个值之前，它必须计算出 factorial(1) 是什么意思。
现在我们有factorial(3)在等待factorial(2)的结果，也就是在等待factorial(1)的结果。 factorial(1) 运行s，并且看到它的输入是 1，所以点击 "else" 块，所以只是 returns 1 到它的调用者，factorial(2)。
现在 factorial(2) 有它需要的东西，return 2 * 1 也可以给它的调用者 factorial(3).
现在 factorial(3) 有它需要的东西，return 3 * 2 也可以给它的调用者。
主叫document.write收到“6”。

递归 "knows" 停止的地方，因为最终它到达一个点，它只是 return 数字 1，而不是 return 依赖于另一个调用 factorial()。如果函数 always 试图调用自身，就没有办法跳出递归循环；它会一直持续下去，直到堆栈溢出。

除了 factorial(1)，每次调用 factorial(n) 都会调用 factorial(n-1) -- 所以请注意 factorial(0) 或 factorial(-1) 或 factorial(1.01) 永远不会达到 1，因此递归只会保持运行ning 直到堆栈溢出。在编写递归函数时，监视和处理永远不会到达出口点的输入是个好主意；在这种情况下，如果输入不是正整数，你会想抛出一个错误。

How come the counter didn't loop lower and how come we never returned to the initial else { return number; } if we called the recursive operation on 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>");

what exactly determines when does recursion stop? When the recursion of the function returns the same result twice (in this case 1?) or is there some different trigger?

尽量不要从某种 "counter" 来跟踪函数何时应该停止递归，或者 "trigger" 主动停止它的角度来考虑这一点——那是误导性的看待方式。该函数的每个实例只知道它收到了什么输入，以及它想要什么 return。大多数时候它想要 return 恰好包含对同一函数的调用，这就是递归的来源；当它想要return 不涉及函数调用时，递归就结束了。

对于这个特定的函数，对于除 1 以外的任何输入，它都会使用输入 n-1 调用自身的一个新实例（并在它可以 return 到其父调用者之前等待结果），所以递归继续。对于1的输入，它不会调用自己，所以递归结束。 'else' 块是您的 "trigger" （不过，再一次，这是一种误导性的思考方式；它不是 "triggering" 任何东西，它只是 returning 一个数字而不是调用return 其结果的函数。）

f(3) 调用 f(2) 调用 f(1) 不调用任何东西。如果您将函数编辑为使用 n+1 而不是 n-1 来调用自身，那么 f(3) 将调用 f(4)，后者将调用 f(5) 等等，直到您运行内存不足。

了解递归背后的执行——递归如何确定何时停止？

Understanding execution behind recursion - how does recursion figure out when to stop?

javascript

recursion

theory