递归简论

eshuex

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

          int
          F( int X )
          {
/* 1 */     if( X == 0)
/* 2 */         return 0;
              else
/* 3 */         return 2 * F( X - 1 ) + X * X
          }

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

             int
             Bad( unsigned int N )
             {
/* 1 */        if( N == 0 )
/* 2 */            return 0;
                 else
/* 3 */            return Bad( N / 3 + 1 ) +      
                     N - 1;
             }

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

不错学习下