了解递归函数是如何工作的

Question

了解递归函数是如何工作的正如标题所解释的那样，我有一个非常基本的编程问题，只是我还不能摸索。过滤掉所有的(非常聪明的)“为了理解递归，你必须首先理解递归。来自各种在线帖子的回复，我仍然不太明白。当我们面对不知道我们不知道的事情时，我们会倾向于提出错误的问题或不正确地提出正确的问题-我会分享我的“想法”，我的问题是希望有类似观点的人能够分享一些知识，帮助我打开递归灯泡！下面是函数(语法用SWIFT编写)：func sumInts(a: Int, b: Int) -> Int {     if (a > b) {         return 0     } else {         return a + sumInts(a: a + 1, b: b)     } }我们将使用2和5作为我们的论点：println(sumInts(a: 2, b: 5))显然答案是14，但我不清楚这个价值是如何实现的。这是我的两个大杂烩：函数被递归调用，直到满足条件为止。该条件为a>b。当满足此条件时，返回0。乍一看，我希望返回值为0，这显然是不正确的。在每次迭代中打印出‘a’值将产生一个我所期望的值：2、3、4、5(在这里，5+1>b满足第一个条件：a>b)，但我仍然不知道如何实现14的值。我的第一个想法是，类似的事情正在神奇地发生：var answer = a; answer += a+1 until a > b; return answer;所以排除魔法，我就是得不到什么。我很想知道发生了什么，而不仅仅是含蓄的。如果有人能很好地解释这种函数在技术上发生了什么，为什么结果不是0，以及最终结果是怎样的，a + sumInts(a: a + 1, b: b) = 14我会永远欠你的。

Answer 1

 想这种混淆是因为把它看作是被多次调用的“相同功能”。如果您认为它是“被调用的同一个函数的许多副本”，那么它可能会更清楚：

只有一个函数的副本返回0，而且它不是第一个(这是最后一个)。所以第一个调用的结果不是0。

至于第二个混乱的地方，我认为用英语拼写递归会更容易一些。读这一行：

return a + sumInts(a + 1, b: b)

作为“返回‘a’+的值(函数的另一个副本的返回值，即‘a’+的副本的值(函数的另一个副本的返回值，它是‘a’+(.)的第二个副本的值”)，函数的每一个副本都会产生一个自身的新副本，a增加1，直到满足a>b条件。

当您到达a>b条件为true时，您有一个(可能任意地)长的函数副本堆栈，所有这些副本都在运行的中间，它们都在等待下一个副本的结果，以找出它们应该添加到‘a’中的内容。

(编辑：另外，需要注意的是，我提到的函数的副本堆栈是一个真正的东西，占用了真正的内存，如果程序太大，就会崩溃。编译器在某些情况下可以优化它，但是在许多语言中，耗尽堆栈空间是递归函数的一个重要而不幸的限制)

Answer 2

1.函数被递归调用，直到满足条件。那个条件是a > b..当满足此条件时，返回0。乍一看，我希望返回值为0，这显然是不正确的。

以下是计算机计算sumInts(2,5)如果它能够：

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

如您所见，对函数的调用sumInts实际上返回0，但这不是最后的值，因为计算机仍然必须将5加到0，然后4到结果，然后3，然后2，正如我们计算机的最后四句话所描述的。注意，在递归中，计算机不仅必须计算递归调用，还必须记住如何处理递归调用返回的值。计算机内存中有一个特殊的区域叫做堆栈在保存此类信息的地方，这个空间是有限的，过于递归的函数可以耗尽堆栈：这是堆栈溢出给我们最爱的网站命名。

你的声明似乎是隐含的假设，即计算机在执行递归调用时忘记了它所处的位置，但它没有，这就是为什么您的结论与您的观察结果不一致的原因。

2.在每次迭代中输出‘a’值将产生一个我所期望的值：2、3、4、5(在这里，5+1>b满足第一个条件：a>b)，但我仍然不知道如何实现14的值。

这是因为返回值不是a的价值之和a和递归调用返回的值。

Answer 3

要理解递归，您必须以不同的方式考虑这个问题。与其从整体上讲有意义的大量逻辑步骤，不如把一个大问题分解成较小的问题，然后解决这些问题，一旦你有了子问题的答案，你就把子问题的结果结合起来，从而解决更大的问题。想想你和你的朋友们，他们需要数一下大桶里弹珠的数量。你做每一件事，拿一个小桶，然后逐个数，当你做完后，你把总数加在一起。好吧，如果你们每个人都找到了一些朋友，然后再把桶分开，那么你只需要等待这些其他的朋友计算出他们的总数，把它拿回给你们每个人，然后把它们加起来。诸若此类。特例是，当你只有一个大理石数，然后你只是返回它，并说1。让其他人做你上面的加法你完成了。

您必须记住，每当函数递归地调用自己时，它就会创建一个包含问题子集的新上下文，一旦该部分得到解决，它就会被返回，以便上一次迭代能够完成。

让我带你看看这些步骤：

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

一旦执行了求和(a：6，b：5)，就可以计算结果，因此可以使用所获得的结果回滚：

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

另一种表示递归结构的方法：

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14