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

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

正如标题所解释的那样,我有一个非常基本的编程问题,只是我还不能摸索。过滤掉所有的(非常聪明的)“为了理解递归,你必须首先理解递归。来自各种在线帖子的回复,我仍然不太明白。

当我们面对不知道我们不知道的事情时,我们会倾向于提出错误的问题或不正确地提出正确的问题-我会分享我的“想法”,我的问题是希望有类似观点的人能够分享一些知识,帮助我打开递归灯泡!

下面是函数(语法用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我会永远欠你的。


慕斯709654
浏览 417回答 3
3回答

千万里不及你

 想这种混淆是因为把它看作是被多次调用的“相同功能”。如果您认为它是“被调用的同一个函数的许多副本”,那么它可能会更清楚:只有一个函数的副本返回0,而且它不是第一个(这是最后一个)。所以第一个调用的结果不是0。至于第二个混乱的地方,我认为用英语拼写递归会更容易一些。读这一行:return a + sumInts(a + 1, b: b)作为“返回‘a’+的值(函数的另一个副本的返回值,即‘a’+的副本的值(函数的另一个副本的返回值,它是‘a’+(.)的第二个副本的值”),函数的每一个副本都会产生一个自身的新副本,a增加1,直到满足a>b条件。当您到达a>b条件为true时,您有一个(可能任意地)长的函数副本堆栈,所有这些副本都在运行的中间,它们都在等待下一个副本的结果,以找出它们应该添加到‘a’中的内容。(编辑:另外,需要注意的是,我提到的函数的副本堆栈是一个真正的东西,占用了真正的内存,如果程序太大,就会崩溃。编译器在某些情况下可以优化它,但是在许多语言中,耗尽堆栈空间是递归函数的一个重要而不幸的限制)

冉冉说

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和递归调用返回的值。

偶然的你

要理解递归,您必须以不同的方式考虑这个问题。与其从整体上讲有意义的大量逻辑步骤,不如把一个大问题分解成较小的问题,然后解决这些问题,一旦你有了子问题的答案,你就把子问题的结果结合起来,从而解决更大的问题。想想你和你的朋友们,他们需要数一下大桶里弹珠的数量。你做每一件事,拿一个小桶,然后逐个数,当你做完后,你把总数加在一起。好吧,如果你们每个人都找到了一些朋友,然后再把桶分开,那么你只需要等待这些其他的朋友计算出他们的总数,把它拿回给你们每个人,然后把它们加起来。诸若此类。特例是,当你只有一个大理石数,然后你只是返回它,并说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
打开App,查看更多内容
随时随地看视频慕课网APP