代码之家 › 专栏 › 技术社区 › Samuel Hulla

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

theory recursion javascript

Samuel Hulla · 技术社区 · 6 年前

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

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

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

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

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

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

调用的函数->加载参数

计算if条件--gt;3>1->应用递归函数

3*递归(2)*递归(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。为什么计数器没有循环下降?为什么我们再也没有回到初始状态? else { return number; } 如果我们调用递归操作 factorial(2-1) 是吗?

这个问题很难用词表达,所以如果你对如何更好地表达它有任何想法,请随意编辑我的问题!

1 回复 | 直到 6 年前

Daniel Beck 6 年前

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

你打电话来 factorial(3) 在你的 document.write() .
因式分解(3) 想要返回 3 * factorial(2) .在返回值之前,必须计算出 factorial(2) 意思是。
所以现在我们有了 因式分解(3) 等待结果 因式分解(2) . 因式分解(2) 跑,想回来 2 * factorial(1) .在返回值之前,必须计算出 factorial(1) 意思是。
现在我们有了 因式分解(3) 等待结果 因式分解(2) ,它正在等待 因式分解(1) . 因式分解(1) 运行,并看到它的输入是1,所以点击“else”块,所以只返回1给它的调用者, 因式分解(2) .
现在 因式分解(2) 有它需要的,所以可以回来 2 * 1 对它的呼叫者来说, 因式分解(3) .
现在 因式分解(3) 有什么? 它需要,所以可以回来 3 * 2 给它的呼叫者。
呼叫 document.write 接收“6”。

递归“知道”在哪里停止,因为它最终到达一个点,它只返回数字1,而不是返回依赖于另一个调用 factorial() .如果函数总是试图调用它自己,就无法退出递归循环;它将一直运行,直到堆栈溢出为止。

除了 因式分解(1) ,每次呼叫 factorial(n) 最后会打电话来 factorial(n-1) --所以请注意 factorial(0) 或 factorial(-1) 或 factorial(1.01) 不会达到1,所以递归将一直运行,直到堆栈溢出。在编写递归函数时,最好注意并处理永远不会到达退出点的输入;在这种情况下,如果输入不是正整数,则希望抛出错误。

如果我们调用factorial上的递归操作(2-1),为什么计数器没有循环降低,为什么我们从未返回到初始else返回数;?

是的,但是你的 文件.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) 直到你的记忆耗尽。