需要一些帮助来理解递归

Need some help to understand recursion

本文关键字：递归 帮助      更新时间：2023-09-26

我正在努力理解递归是如何工作的。我知道了基本的想法，但细节还不清楚。以下是javascript中的一个简单示例：

function sumTo(n){
    if (n > 1){
        return n + sumTo(n-1)
    } else {
        return n
    }
}
sumTo(3);

它应该计算3中的所有数字，结果是6（1+2+3=6），但我不明白它是如何工作的。

好的，我们从if条件开始。3>1，所以我们返回n并再次调用该函数，但如果括号内有什么？

它看起来像这样吗：

3+sumTo（2）//3-1=2

或者我们对n什么都不做，等待下一个函数：

3+sumTo（n-1）//n稍后将出现

有人告诉我，最后一个函数会将1返回到上一个，但我不知道它会如何处理这个1。

如果对终极假人有一些循序渐进的解释，请分享。

我知道有很多类似的问题，但没有找到任何帮助。

UPD:我花了两天时间，尽我所能询问了所有人，似乎终于找到了它的工作原理。我会努力为像我这样的终极傻瓜解释。这会很长时间，但我希望有同样问题的人能找到这篇帖子，它会很有用。

首先，我想展示另一个递归的例子，它稍微简单一点。我在http://www.integralist.co.uk/posts/js-recursion.html并将值从（1，10）更改为（2，3）。

function sum(x, y) {
    if (y > 0) {
      return sum(x + 1, y - 1);
    } else {
      return x;
    }
}
sum(2, 3);

当我们启动函数时，我们检查是否条件y>0。Y是3，所以条件成立。所以我们返回sum（x+1，y-1），即sum（2+1，3-1），即和（3，2）。

现在我们需要计算sum（3，2）。再次，我们回到开始，从条件y>0开始。Y是2，所以条件成立。所以我们返回sum（x+1，y-1），即sum（3+1,2-1），即和（4,1）。

现在我们需要计算sum（4,1）。再一次，我们检查条件y>0。Y为1，则条件为true。我们返回sum（x+1，y-1），即sum（4+1，1-1），即和（5,0）。

现在我们需要计算sum（5，0）。我们检查条件y>0，它是错误的。根据函数中的if-else，我们返回x，它是5。因此，sum（2，3）返回5。

现在让我们对sumTo（）做同样的操作；

function sumTo(n){
    if (n > 1){
        return n + sumTo(n-1)
    } else {
        return n
    }
}
sumTo(3);

从sumTo（3）开始。检查n>1条件：3>1为真，因此我们返回n+sumTo（n-1），即3+sumTo（3-1），即3+sumTo（2）。

要继续，我们需要计算sumTo（2）

要做到这一点，我们再次从检查n>1条件开始函数：2>1为真，因此我们返回n+sumTo（n-1），即2+sumTo（2-1），即2+sumTo（1）。

要继续，我们需要计算sumTo（1）

为此，我们再次启动函数并检查n>1条件。1>1是false，因此，根据if-else，我们返回n，即1。因此，sumTo（1）得到1。

现在我们将sumTo（1）的结果传递给上函数sumTo（2），我们之前曾说过，我们需要sumTo（1）才能继续。

SumTo（2）返回n+SumTo（n-1），即2+SumTo（2-1），即2+SumTo（1），也就是2+1。因此，sumTo（2）得到3。

现在我们将sumTo（2）的结果传递给上函数sumTo（3），我们之前说过需要sumTo（1）才能继续。

SumTo（3）返回n+SumTo（n-1），即3+SumTo（3-1），即3+SumTo（2），即2+3。因此，sumTo（3）最终得到6。因此，sumTo（3）返回6。

我的错误是，在所有地方我都试图插入3而不是n，而n正在减少到1。

感谢所有回答这个问题的人。

你可以像一样理解

sumTo(3);
returns => 3 +  sumTo(2) // n is greater than 1
                returns => 2 +  sumTo(1)
                                returns => 1 // 1 as n is not greater than 1

没错，sumTo(n)一直等到sumTo(n-1)完成。
因此，sumTo(3)等待sumTo(2)，
sumTo(2)等待sumTo(1)，
则sumTo(1)返回1，
sumTo(2)返回2 + 1
并且CCD_ 11返回CCD_

显示工作：

sumTo(4) = (4 + 3) + (2 + 1) = 10 // 4 + sumTo(3). function called four times
sumTo(3) = (3 + 2) + 1       = 6  // 3 + sumTo(2). called three times
sumTo(2) = (2 + 1)           = 3  // 2 + sumTo(1). called twice
sumTo(1) = (1)               = 1  // called once

如果你向后想，从头开始，而不是从上往下想，你可能会更容易把头裹起来。像这样：

sumTo(1) = 1 + sumTo(0) = 1
sumTo(2) = 2 + sumTo(1) = 3
sumTo(3) = 3 + sumTo(2) = 6
sumTo(4) = 4 + sumTo(3) = 10

请注意，现在您可以继续添加到列表中，并且很容易计算前一个，因为您只需添加两个和。

事件链如下：

sumTo(3)加3并调用sumTo(2)，后者也调用sumTo(1)并返回3，总共得到6。

这有道理吗？如果有人有问题，我很乐意详细说明或澄清。需要理解的一个重要问题是为什么使用递归，以及何时何时使用递归。关于这个主题的一个很好的讨论可以在这里找到：什么时候使用递归？

递归的一个经典例子是fibonacci序列。另一个很好的例子是遍历计算机上的文件目录，例如，如果你想搜索包含其他文件夹的文件夹中的每个文件。您也可以使用递归来对指数进行因子化。

考虑一个更简单的递归示例：

function multiplyBy10(i) {
    if ( !i ) return 0;
    return 10+multiplyBy10(i-1);
}

此函数将使用递归将数字乘以10。掌握递归何时实用是件好事，因为有时它会让事情变得更容易。然而，最好保持简单，尽可能不要混淆自己。：）

相关文章：