function - 了解递归函数的工作原理

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。但我不清楚这个值是如何实现的。

这是我的两个难题:

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

2. 在每次迭代中打印出“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 code>，我将永远欠你的情。

Answer 1

1.The function is called recursively until a condition is met. That condition is a > b. When this condition is met, return 0. At first glance, I would expect the return value to be 0 which is obviously incorrect.

如果计算机能够计算 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.Printing out the value of 'a' on each iteration yields a value which I would expect: 2, 3, 4, 5 (at which point 5+1 > b which meets the first condition: a > b) but I still don't see how the value of 14 is achieved.

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