递归简论
本帖最后由 eshuex 于 2017-6-15 14:36 编辑递归的四条基本法则：
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)的计算。
{:5_102:} 这个牛！ 小甲鱼 发表于 2017-6-16 18:09
这个牛！
谢谢甲鱼哥，内容来自《数据结构与算法分析--C语言描述》，我只是学习的同时做一下整理。 不错学习下
页:
[1]