递归简论

eshuex

递归的四条基本法则：
1．基准情形。必须有基准情形，无需递归就能解出。
2．不断推进。对于需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
3．设计法则。假设所有的递归调用都能运行。
4．合成效益法则。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。

1.           int
   
2.           F( int X )
   
3.           {
   
4. /* 1 */     if( X == 0)
   
5. /* 2 */         return 0;
   
6.               else
   
7. /* 3 */         return 2 * F( X - 1 ) + X * X
   
8.           }

复制代码

法则解释：
1．基准情形。
        第一行和第二行处理基准情况，若没有F(0)=0这个条件，此函数将不会终止。
2．不断推进。
        第三行执行，递归调用反复进行，每次调用总能够朝基准情形推进，直到基准情形出现。需要注意的是递归调用出现死循环，无法调用基准。
        例如：

1.              int
   
2.              Bad( unsigned int N )
   
3.              {
   
4. /* 1 */        if( N == 0 )
   
5. /* 2 */            return 0;
   
6.                  else
   
7. /* 3 */            return Bad( N / 3 + 1 ) +      
   
8.                      N - 1;
   
9.              }

复制代码

3．设计法则。
        假设所有的递归调用都能运行。不要试图追踪大量的递归调用，这是非常困难的。
4．合成效益法则。
        将在后面的章节给予证明。

使用误区：
1．对于数值计算，使用递归通常不是好主意。
2．递归绝不应该作为简单for循环的替代物，好的递归很难转换成for循环。

常见问题：
1．递归是否是循环逻辑？
答：虽然递归调用了递归函数本身，但并没有用函数本身定义该函数的一个特定的实例。例如通过使用F(5)来得到F(5)的值才是循环，通过F(4)得到F(5)的值不是循环，除非F(4)的求值又用到了对F(5)的计算。

小甲鱼

这个牛！

eshuex

小甲鱼 发表于 2017-6-16 18:09
这个牛！

谢谢甲鱼哥，内容来自《数据结构与算法分析--C语言描述》，我只是学习的同时做一下整理。

johnw

不错学习下