Question

如何写递归函数

Answer 1

一句话搞掂.

如果一个函数里面包含了一个步骤,这个步骤的里面的步骤是和这个函数的所有步骤是一致的,那么这个函数就是递归函数.理解了我这句话,递归算法的应用就不是问题了.

写递归函数第一步是分析问题,分析问题是否存在"一个函数里面包含了一个步骤,这个步骤的里面的步骤是和这个函数的所有步骤是一致的"这种关系,如果存在,使用递归函数必定是成功的,因为它就是递归函数的定义的阐发.

看我分析最经典的汉诺塔问题:

将n个盘从第1个柱子移到第3个柱子需要三步完成,换句话说,这个移盘函数---用f来表示,它由三步完成.

1. 将n-1个盘从第1个柱子移到第2个柱子.
   

2. 将1个盘从第1个柱子移到第3个柱子

3. 将n-1个盘从第2个柱子移到第3个柱子.

关键的地方到了,如果一个函数里面包含了一个步骤,这个步骤的里面的步骤是和这个函数的所有步骤是一致的,

看第1个步骤,将n-1个盘从第1个柱子移到第2个柱子,我们暂时用g来表示,等下你会发现f=g的.

这个步骤也是由3个步骤来完成的:

1.将n-2个盘从第1个柱子移到第3个柱子.

2.将1个盘从第1个柱子移到第2个柱子

3.将n-2个盘从第3个柱子移到第2个柱子.

首先"将n-1个盘从第1个柱子移到第2个柱子" 是 "将n个盘从第1个柱子移到第3个柱子" 的一个步骤.

其次"将n-1个盘从第1个柱子移到第2个柱子" 这个步骤  包含的步骤  是和 "将n个盘从第1个柱子移到第3个柱子"这个函数的步骤是一致的(都是三步),只是柱子的位置不同而已,这里的位置和函数的参数是等价的,因此,位置不同,就是函数参数值不同而已,函数的参数个数就等价于柱子的个数.换句话说,f和g的步骤和参数是一致的,只是实参不同而已,因此f=g的.这里面涉及到一点抽象思维,只能靠自己去理解了.

因此,如果用f(n,a,b,c)表示将n个盘从第1个柱子移到第3个柱子的话,那么,将n-1个盘从第1个柱子移到第2个柱子,就可以用f(n-1,a,c,b)表示了,为什么?因为上述已经分析过了,步骤是一致的,参数的个数是一致的,只是参数的值不同而已.

我总结了一个最快完成递归函数的方法,做一道题大概5分钟左右.

1. 当n时,需要的步骤,列出来
   

2. 当n-1时,需要的步骤,列出来.

比较上述两者的共性:1.步骤是一致的,2.参数的个数是一致的

如果满足上述两者,就将n-1的步骤就n的步骤代替,这样就ok了.

Answer 2

递归函数，是指某一函数内部自己直接或间接地调用自己，即直接递归和间接递归。是语言中比较高级的技术用法。 递归函数之所以难，是因为是一种过于抽象化的技术 ，写代码的时候无法直观的看出逻辑是否符合自己要求，因此想一次性写好递归函数，是一件很困难的事情，必须要程序运作起来执行递归函数的代码才能看出是否正确，而且进行测试的难度也很高，有时的隐含bug可能要软件上线后才会渐渐体现出来。 首先， 要分析清楚满足递归的条件，并一一列出。 其次， 要分析不满足条件时的处理方式。 在列出了所有条件后，我们自然还要考虑不满足条件后的结果，一种是业务本身要求的不满足条件后的处理，另一种就是出现错误时候的处理。说的简单点，就是正确的情景考虑到了后还要考虑错误的情景。 接下来， 要分析递归函数的返回值。 最后， 写完递归函数后一定要进行单元测试，测试也要有方法。 因此难以保障一次写完后正确性，所以写完后一定要测试，递归函数本身测试也很麻烦，递归次数少倒还好，递归次数一旦多的话就很头疼。这时我们可以将循环的次数，以及递归的后的结果打印出来，看看打印后的结果是否符合自己的预期，如果某一递归出现问题，可以根据循环次数的记录在调试的时候直接定位，这样效率会高很多，也容易很多，要不然一步步调试看，实在是折磨人。测试的时候一定要涉及到所有满足递归的条件，每一条件分支都要检查一遍，这样才是较为全面的测试递归的方法。 写递归函数，不是一下两下能搞定的事情，本身就是一个反复性工作，编写→测试→编写→测试→...，所以在分析、编写的时候一定要静心、细心，不要急躁，这样渐渐的递归函数也就健全起来。头几次写递归函数可能写不好，日后多多练习便会慢慢深刻体会到递归的精髓。 那么我想说的也说完了，希望这篇文章能对大家有帮助。