了解递归函数的工作原理

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,我将永远负债累累.

Answer 1

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但是这不是最终值,因为计算机仍然必须向该0添加5,然后4到结果,然后是3,然后是2,如最后四个句子所描述的我们电脑的想法.请注意,在递归中,计算机不仅必须计算递归调用,还必须记住如何处理递归调用返回的值.计算机存储器的一个特殊区域称为堆栈,其中保存了这种信息,这个空间是有限的,过于递归的功能可能耗尽堆栈:这是堆栈溢出,它的名字给我们最喜欢的网站.

你的陈述似乎暗示了计算机忘记了在进行递归调用时所处的状态,但事实并非如此,这就是为什么你的结论与你的观察结果不符的原因.

2.在每次迭代中打印出'a'的值会产生一个我期望的值:2,3,4,5(此时5 + 1> b满足第一个条件:a> b)但我仍然看不出14的价值是如何实现的.

这是因为返回值不是a自身,而是a递归调用返回的值和值的总和.

Answer 2

我认为混淆源于将其视为多次调用的"同一功能".如果你认为它是"被调用的同一函数的许多副本",那么它可能更清楚:

只有该函数的一个副本返回0,并且它不是第一个(它是最后一个).所以调用第一个的结果不是0.

对于第二点困惑,我认为用英语拼出递归会更容易.阅读此行:

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

as"返回'a'加值的值(该函数的另一个副本的返回值,这是'a'加号的副本值(该函数的另一个副本的返回值,这是第二个副本的值') a'加号(......),函数的每个副本产生一个新的副本,增加1,直到满足a> b条件.

当你到达a> b条件为真时,你有一个(可能是任意)长的函数副本堆栈,所有这些都在运行的中间,所有等待下一个副本的结果,找出它们是什么应该添加到'a'.

(编辑:另外,要注意的是,我提到的函数的副本堆栈是一个真实的东西,占用了实际的内存,并且如果程序变得太大会使程序崩溃.编译器可以在某些程序中优化它但是,在许多语言中,耗尽堆栈空间是递归函数的一个重要且不幸的限制)

Answer 3

要理解递归,您必须以不同的方式考虑问题.而不是整个有意义的大步骤的逻辑顺序,而是一个大问题,分解成更小的问题并解决这些问题,一旦你有子问题的答案,你结合子问题的结果,使解决更大的问题.想想你和你的朋友需要在一个巨大的桶中计算弹珠的数量.你们每个人都拿一个较小的水桶然后单独统计这些水桶,当你完成后,你们将总数加在一起..现在,如果你们每个人找到一些朋友并进一步拆分水桶,那么你只需要等待这些其他朋友来找出他们的总数,把它带回给你们每个人,你把它加起来.等等.特殊情况是当你只得到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 4

递归是一个难以理解的主题,我不认为我可以在这里完全正义.相反,我将尝试专注于您在此处的特定代码片段,并尝试描述解决方案工作原理的直觉以及代码如何计算其结果的机制.

您在此处给出的代码解决了以下问题:您想知道从a到b的所有整数的总和.对于您的示例,您希望数字的总和从2到5(包括两者),即

2 + 3 + 4 + 5

当试图递归地解决问题时,最初的步骤之一应该是弄清楚如何将问题分解为具有相同结构的较小问题.因此,假设您想要总结从2到5的数字,包括两者.简化这一点的一种方法是注意上述总和可以重写为

2 +(3 + 4 + 5)

这里,(3 + 4 + 5)碰巧是3和5之间所有整数的总和,包括3和5.换句话说,如果你想知道2和5之间所有整数的总和,首先计算3和5之间所有整数的总和,然后加2.

那么如何计算3到5之间所有整数的总和？嗯,那个数字是

3 + 4 + 5

这可以被认为是

3 +(4 + 5)

这里,(4 + 5)是4和5之间所有整数的总和,包括4和5.因此,如果要计算3到5之间所有数字的总和(包括3和5),则计算4到5之间所有整数的总和,然后加3.

这里有一个模式!如果要计算a和b之间的整数之和,则可以执行以下操作.首先,计算a + 1和b之间的整数之和.接下来,添加一个总数.您会注意到"计算+ 1和b之间的整数之和,包括"恰好是我们已经尝试解决的问题,但参数略有不同.我们不是从a到b计算包容性,而是从+ 1到b进行计算.这是递归步骤 - 为了解决更大的问题("从a到b的总和"),我们将问题简化为更小的版本("从+ 1到b的总和,包括在内").

如果您查看上面的代码,您会发现其中有以下步骤:

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

这段代码只是上述逻辑的翻译 - 如果你想要从a到b的总和,从开头算起一个+ 1到b,包括(这是对sumInts 的递归调用),然后加上a.

当然,这种方法本身并不起作用.例如,如何计算5到5之间所有整数的总和？好吧,使用我们当前的逻辑,你可以计算6到5之间所有整数的总和,然后加上5.那么你如何计算6到5之间所有整数的总和(包括6和5)？好吧,使用我们当前的逻辑,你可以计算7到5之间所有整数的总和,然后加6.你会发现这里有一个问题 - 这只是继续前进和前进!

在递归问题解决中,需要有一些方法来停止简化问题,而只是直接解决它.通常情况下,您会发现一个简单的案例,可以立即确定答案,然后构建解决方案,以便在出现简单案例时直接解决.这通常称为基本情况或递归基础.

那么这个特定问题的基本情况是什么？当你总结从a到b的整数时,如果a恰好大于b,那么答案就是0 - 范围内没有任何数字!因此,我们将按如下方式构建我们的解决方案:

1. 如果a> b,则答案为0.
2. 否则(a≤b),得到如下答案:
   1. 计算a + 1和b之间的整数之和.
   2. 添加一个以获得答案.

现在,将此伪代码与您的实际代码进行比较:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

请注意,伪代码中概述的解决方案与此实际代码之间几乎完全是一对一的映射.第一步是基本情况 - 如果你要求空数范围的总和,你得到0.否则,计算a + 1和b之间的总和,然后去添加a.

到目前为止,我只给出了代码背后的高层次想法.但是你有两个非常好的问题.首先,为什么不总是返回0,假设函数说如果a> b则返回0？其次,14实际上来自哪里？让我们依次看看这些.

让我们尝试一个非常非常简单的案例.如果你打电话sumInts(6, 5)会怎么样？在这种情况下,通过代码进行跟踪,您会看到函数只返回0.这是正确的做法, - 范围内没有任何数字.现在,努力尝试一下.你打电话sumInts(5, 5)怎么办？嗯,这是发生的事情:

1. 你打电话sumInts(5, 5).我们落入else分支,它返回"a + sumInts(6,5)"的值.
2. 为了sumInts(5, 5)确定是什么sumInts(6, 5),我们需要暂停我们正在做的事情并拨打电话sumInts(6, 5).
3. sumInts(6, 5)被叫.它进入if分支并返回0.但是,这个实例sumInts被调用sumInts(5, 5),因此返回值被传递回sumInts(5, 5),而不是传递给顶级调用者.
4. sumInts(5, 5)现在可以计算5 + sumInts(6, 5)回来了5.然后它将它返回给顶级调用者.

注意这里是如何形成值5的.我们从一个活跃的电话开始sumInts.这启动了另一个递归调用,该调用返回的值将信息传回sumInts(5, 5).然后对sumInts(5, 5)then 的调用进行了一些计算并将值返回给调用者.

如果你试试这个sumInts(4, 5),这将是会发生什么:

• sumInts(4, 5)试图回来4 + sumInts(5, 5).要做到这一点,它会调用sumInts(5, 5).
  • sumInts(5, 5)试图回来5 + sumInts(6, 5).要做到这一点,它会调用sumInts(6, 5).
  • sumInts(6, 5)将0返回到sumInts(5, 5).</li> <li>sumInts(5,5)now has a value forsumInts(6,5), namely 0. It then returns5 + 0 = 5`.
• sumInts(4, 5)现在有一个值sumInts(5, 5),即5.然后返回4 + 5 = 9.

换句话说,返回的值是通过一次一个地对值进行求和而形成的,每次取一个特定递归调用返回的值sumInts并添加当前值a.当递归触底时,最深的调用返回0.但是,该值不会立即退出递归调用链; 相反,它只是将值交还给它上面一层的递归调用.以这种方式,每个递归调用只增加一个数字并在链中返回更高的数字,最终得到总和.作为练习,尝试追踪这个sumInts(2, 5),这是你想要开始的.

希望这可以帮助!

Answer 5

到目前为止,你已经得到了一些很好的答案,但是我会再添加一个不同的方法.

首先,我写了许多关于简单递归算法的文章,你可能会感兴趣; 看到

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

这些是最新的订单,所以从底部开始.

其次,到目前为止,所有答案都通过考虑函数激活来描述递归语义.每个调用都会进行一次新的激活,并且递归调用将在此激活的上下文中执行.这是一种思考它的好方法,但还有另一种等效方式:智能文本搜索和替换.

让我把你的功能重写成一个稍微紧凑的形式; 不要认为这是任何特定的语言.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

我希望这是有道理的.如果您不熟悉条件运算符,那么它就是形式condition ? consequence : alternative,其含义将变得清晰.

现在,我们希望评估s(2,5) 做的文本替换为函数体的通话,然后更换我们这样做,a有2和b有5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

现在评估条件.我们以文字替换2 > 5用false.

---> false ? 0 : 2 + s(2 + 1, 5)

现在以文本方式将所有错误条件替换为替代和所有具有结果的真实条件.我们只有错误的条件,所以我们用替代方法用文本替换该表达式:

---> 2 + s(2 + 1, 5)

现在,为了省去我必须键入所有这些+符号,文本上用它的值替换常量算术.(这有点像作弊,但我不想跟踪所有的括号!)

---> 2 + s(3, 5)

现在搜索和替换,这次是与呼叫的主体,3for a和5for b.我们将把括号中的替换置于括号中:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

现在我们继续做同样的文本替换步骤:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

我们在这里所做的只是简单的文本替换.真的,我不应该用"3"代替"2 + 1"等等,直到我不得不这样做,但教学上它本来难以阅读.

函数激活只不过是将函数调用替换为调用体,并将形式参数替换为相应的参数.你必须小心谨慎地引入括号,但除此之外,它只是文本替换.

当然,大多数语言实际上并不实现激活作为文本替换,但从逻辑上讲它就是它的本质.

那么什么是无限递归呢？文本替换不会停止的递归!注意我们最终如何进入一个没有更新的步骤s,然后我们可以只应用算术规则.

Answer 6

我通常弄清楚递归函数如何工作的方式是查看基本情况并向后工作.这是应用于此功能的技术.

首先是基本情况:

sumInts(6, 5) = 0

然后在调用堆栈中的调用之上调用:

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

然后在调用堆栈中的调用之上调用:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

等等:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

等等:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

请注意,我们已经达到了对函数的原始调用 sumInts(2, 5) == 14

执行这些调用的顺序:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

这些调用返回的顺序:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

请注意,我们通过按照返回的顺序跟踪调用来得出关于函数如何操作的结论.

Answer 7

我会试一试.

执行等式a + sumInts(a + 1,b),我将展示最终答案是14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

如果您有任何其他问题,请告诉我们.

这是以下示例中的递归函数的另一个示例.

一个人刚刚大学毕业.

t是以年为单位的时间量.

退休前的实际工作总年数,可计算如下:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

这应该足以压抑任何人,哈哈.;-P

Answer 8

递归.在计算机科学中,在有限自动机的主题下深入介绍了递归.

最简单的形式是自我参考.例如,说"我的车是汽车"是递归声明.问题是该语句是无限递归,因为它永远不会结束."汽车"声明中的定义是它是"汽车",因此它可以被替换.然而,没有尽头,因为在替代的情况下,它仍然变成"我的车是汽车".

如果声明是"我的车是宾利车,我的车是蓝色的",这可能会有所不同.在这种情况下,在第二种情况下,汽车的替代可以是"宾利",导致"我的宾利是蓝色的".这些类型的替换在计算机科学中通过无上下文语法进行数学解释.

实际替换是生产规则.鉴于该语句由S表示并且该汽车是可以是"bentley"的变量,该语句可以递归地重构.

S -> "my"S | " "S | CS | "is"S | "blue"S | ?
C -> "bentley"

这可以以多种方式构建,因为每种|方式都有选择.S可以被这些选择中的任何一个替换,并且S总是从空开始.?终止生产的手段.正如S可以替换的那样,其他变量也是如此(只有一个变量,它C代表"bentley").

所以从S空的开始,用第一个选择替换它就"my"S S变成了

"my"S

S仍然可以替换,因为它代表一个变量.我们可以再次选择"我的",或者ε来结束它,但让我们继续制作我们的原始陈述.我们选择意味着S被替换的空间" "S

"my "S

接下来让我们选择C.

"my "CS

C只有一个替代选择

"my bentley"S

而S的空间又来了

"my bentley "S

等等"my bentley is"S,"my bentley is "S,"my bentley is blue"S,"my bentley is blue"(用于更换εs结尾生产),我们已经建立递归我们的发言"我的宾利是蓝色的".

将递归看作这些产品和替代品.该过程中的每个步骤都会替换其前一步,以产生最终结果.在从2到5的递归和的确切示例中,您最终得到了生产

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

这变成了

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

Answer 9

我知道有点离题，但是...尝试在 Google 中查找递归...您会通过示例看到它的含义:-)

早期版本的 Google 返回以下文本（从内存中引用）：

递归

参见递归

2014年9月10日，关于递归的笑话更新了：

递归

您的意思是：递归

其他回复请参阅此答案。

Answer 10

我在学习和真正理解递归时遇到的一个非常好的技巧是花一些时间学习一种除了通过递归之外没有任何形式的循环结构的语言。这样你就会对如何通过实践使用递归有一个很好的感觉。

我关注了http://www.htdp.org/，它不仅是一个 Scheme 教程，还很好地介绍了如何在架构和设计方面设计程序。

但基本上，你需要投入一些时间。如果没有“牢固”掌握递归，某些算法（例如回溯）在您看来总是“困难”甚至“神奇”。所以，坚持。:-D

我希望这个帮助能祝你好运！

Answer 11

将递归视为做同一件事的多个克隆......

你要求克隆[1]：“2到5之间的数字总和”

+ clone[1]               it knows that: result is 2 + "sum numbers between 3 and 5". so it asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           it knows that: result is 3 + "sum numbers between 4 and 5". so it asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       it knows that: result is 4 + "sum numbers between 5 and 5". so it asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   it knows that: result is 5 + "sum numbers between 6 and 5". so it asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] it knows that: it can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   it gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       it gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           it gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               it gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

瞧！！