递归：参见“递归”

递归：参见“递归”

（递归的定义：如题）

 

总体分析：

　　递归算法的效率是极低的（众所周知，函数调用是要耗费较多计算机资源的，而递归也是一种函数调用）。很多情况下，递归耗费的时间和占用的存储空间都要比非递归算法多。从我做的题目来说，递归规模稍微大点儿就已经TLE或爆栈了，如果你用过递归的方法求Fibbonacci Number你就知晓，当规模仅仅是50就暴慢啦，看着输出控制台憋了半天硬是没有把计算结果给憋出来啊，而非递归对此表示毫无压力。递归利用了堆栈段，由此就延伸出一雷区——递归里面开了大数组。要知道，局部变量都是放在堆栈段里的，递归里面开大数组会大大增加程序灭亡的风险。这里其实就牵涉到一个原则，大数组应该放在main函数外，也就是设置成全局变量，会更惬意。绝大多数的递归算法都可以转换为非递归的方式，当追求高效率时，不妨将递归算法稍微改改，自己去构造一个栈区，就可以改成非递归了。

有这样一个递归函数:

        f(n){
             ...;
             f(n-1);
             f(n-2);
             ...;
         }

 

      以前自己研究递归代码或写递归算法时容易陷入一个思维定势：每次在主递归函数内部遇到被调用函数的时候，思维总是先一层层深入（比如遇到f(n-1)，就会先在脑海中把它递归一遍），递归想通后再回到主递归函数（进行到f(n-2))，然后再继续……这样“有时候”是可以将这个算法理解的，但是最后会发现脑子乱成一团麻，这样就悲剧啦，递归算法就是让思路更清晰的啊。

      后来，上面这个函数变成这样读的：从f(n)进来，然后遇到f(n-1),已经了解了f(n-1)有什么一个功能，然后直接读到f(n-2)……这种想法是先总体，再细致。为什么要先总体？因为每一层递归调用函数都是完整的，如果思维是先细致再总体，很容易掉进深渊找不着北，呼吁尊重函数的完整性有木有啊！

　　有一次，自己写出如下形式代码，现在看都一身汗啊：

         f(int n){
                int i;
                for(i=0;i<n;i++){
                    f(i);
               }
           }

 

　　   发现递归里面循环递归绝对杀伤脑细胞。如果想用上面循环递归的形式，不妨多想想是否可以是像Fibbonacci那样两项递归会更怡人。

 

一类常见问题：

 

1）直线切分平面

　　问题描述：n条直线，最多可以把平面分为多少个区域?
 

 

　　析:可能你以前就见过这题目，这充其量是一道初中的思考题。但这一个类型的题目还是从简单的入手，才容易发现规律。当有n-1条直线时，平面最多被分成了f(n-1)个区域。则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。而每条射线和线断将以有的区域一分为二。这样就多出了2+(n-2)个区域。
故：

　　f(n) = f(n-1) + n

写成对n的函数：

　　f(n) = f(n-1)+n

　　　　 = f(n-2)+(n-1)+n
　　　　 …
　　　　 =2+2+…+n
　　　　 =n(n+1)/2+1

 

2）折线分平面

　　问题描述：n条折线，最多可以把平面分为多少个区域?

 

　　析：根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f(n-1)。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，即2*(n-1)条线段相交。那么新增的线段数为

4*(n-1)，射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。

故：

　　f(n)=f(n-1)+4(n-1)+2-1

写成对n的函数：

　　=f(n-1)+4(n-1)+1
　　=f(n-2)+4(n-2)+4(n-1)+2
　　…
　　=f(1)+4+4*2+…+4(n-1)+(n-1)
　　=2n^2-n+1

 

3）封闭曲线分平面问题
　　问题描述：设有n个圆画在平面上，而任何两个恰好相交于两点，且任何三个圆不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

　　析：当n-1个圆时，区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交，则第n个圆被分为2（n-1）段线段，增加了2(n-1)个区域。
故：

　　f(n)=f(n-1)+2(n-1)

对n的函数为：f(n)=n^2-n+2

 

4）三角形切分平面

　　问题描述：用N个三角形最多可以把平面分成几个区域?

　　析：这题和直线切割平面的问题类似，当放第n个三角形的时候，这第n个三角形的每条边都和前n-1个三角形的一个尖角相交则这条边上产生2*(n-1)个交点，那么这个三角形一共有3*2*(n-1)个交点（我们知道，多出多少条线段，平面就被多分割出多少个部分）也就推出整个三角形被分割成3*2*(n-1)个部分（顶点不算交点），每个部分可以看成是一条线段，那么整个平面就多出了 3*2*(n-1) 个部分，完成

有：

　　f(1)=2
　　f(n)=f(n-1)+3*2*(n-1)

转换为：f(n)=2+3*n*(n-1)

　　从上面四种情况可以看出，假设我们已经知道规模为1或2的情况,并且知道了规模为n-1的情况，当规模加1达到n时会引起什么额外的变化，是关键要考虑的,也就是如上述例子所说会增加多少个交点、增加多少调公共边，这个变化我们设为x，那么就很容易得到：

　　　　　　　　　　　　　f(n)=f(n-1)+x

　　上面的分析方法实际称作“递推”,这是一种从最基础、能目测的情况出发，推出规模为n时事件的结果的方法。递推和递归有很多相似之处，也许没有必要刻意把界限划分清楚。

 

 

　 递推可以看作是递归的反向。利用现有信息得到新信息，是递推的精髓。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　                                                                                   ——摘自佳爷的黑书

 

 

递推引发的思考

　　递推的定义不难理解，困难就在如何从已知信息逐步推出后续信息。比如Fibonacci number（请允许我再次调用这万众皆知的家伙），我们看大兔生小兔的过程，1个兔，2个兔，3个兔，5个兔……生着生着规律就被Fibonacci总结出了，结果是喜人的，但过程是残酷的。

　　从已知信息得出规律才是递归的真正核心，一旦了解了规律，推出了公式，问题就迎刃而解了。很多事情说易做难，规律题往往让人痛不欲生啊有木有，如果想很快发现规律，自身各方面知识必须足够强大啊，各种组合数学、图论、数论、概率论，各种公式定理必须齐上阵啊，最蛋疼的有时候物理化学也来凑热闹啊有木有！

最后，我觉得，递推只是一种思考方式，而它本身是没有统一的公式的，每一道递推题都可以包含不同的规律。但是递推题也是最有意思的，能用一种很简单的规律或一条很简洁的公式去解决复杂的问题，自豪感必须倍增啊！！！

　　补数学去~~~

评论

2 楼 nwsuafer 2012-04-26  

补数学去

1 楼 kidding87 2012-04-26  

博主最后一句话太有喜感了~