了解递归函数的工作原理

Question

正如标题所解释的，我有一个非常基本的编程问题，但我还没有找到。过滤掉所有（非常聪明的）“为了理解递归，你必须首先理解递归。”各种在线线程的回复我仍然不太明白。

当我们面对不知道自己不知道的事情时，我们可能会提出错误的问题或错误地提出正确的问题。我将分享我的“想法”。我的问题是希望有类似观点的人能够分享一些知识，帮助我打开递归灯泡！

以下是html" target="_blank">函数（语法用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”的值会产生一个我期望的值：2，3，4，5（此时5.1

我的第一个想法是，类似以下的事情正在神奇地发生：

var answer = a;
answer += a+1 until a > b;
return answer;   

所以排除魔法，我只是没有得到什么。我想了解正在发生的事情，而不仅仅是隐含的。

如果有人能善意地解释一下在这种函数中技术上发生了什么，为什么结果不是0，以及最终如何将一个sumits（a:a 1，b:b）=14，我将永远欠你的债。

Answer 1

要理解递归，你必须以不同的方式思考问题。不是一个整体上有意义的大逻辑步骤序列，而是一个大问题，分解成更小的问题并解决这些问题，一旦你对子问题有了答案，你就结合子问题的结果来解决更大的问题。想想你和你的朋友需要在一个大桶里数弹珠的数量。你们每个人都拿一个更小的桶，然后单独去数，当你完成时，你把总数加在一起...现在，如果你们每个人都找到一些朋友，把桶进一步分开，那么你只需要等其他朋友算出他们的总数，把它拿回来给你们每个人，你把它加起来。以此类推。特殊情况是，当你只有1个大理石要数，然后你把它退回来，说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

一旦执行了sumInts（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 

Answer 2

我认为这种混乱源于将其视为多次调用的“同一个函数”。如果你把它想象成“同一个函数的许多副本被调用”，那么可能会更清楚：

只有一个函数的副本返回0，并且它不是第一个（它是最后一个）。所以调用第一个的结果不是0。

对于第二点困惑，我认为用英语拼写递归会更容易。阅读这一行：

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

as“return the value of‘a’plus（函数的另一个副本的返回值，即‘a’plus的副本值）（函数的另一个副本的返回值，即‘a’plus的第二个副本值（…）”，随着函数的每个副本生成自身的新副本，a增加1，直到a

当你到达a时

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

Answer 3

递归调用函数，直到满足条件。这种情况是

以下是计算机计算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.

如你所见，一些对函数sumits的调用实际上返回0，但这不是最终值，因为计算机仍然需要在0上加5，然后在结果上加4，然后加3，然后加2，正如我们计算机思想的最后四句所描述的那样。注意，在递归中，计算机不仅必须计算递归调用，还必须记住如何处理递归调用返回的值。计算机内存中有一个特殊的区域叫做堆栈，在那里保存此类信息，这个空间是有限的，过于递归的函数可能会耗尽堆栈：这是堆栈溢出，为我们最喜欢的网站命名。

你的陈述似乎隐含了这样一个假设，即计算机在进行递归调用时忘记了它所处的位置，但事实并非如此，这就是为什么你的结论与你的观察结果不匹配。

2.在每次迭代中打印出“a”的值会产生一个我期望的值：2、3、4、5（此时5 1

这是因为返回值不是a本身，而是a的值和递归调用返回的值的总和。