- 递归的基本概念:程序调用自身的编程技巧称为递归,是函数自己调用自己。
- 使用递归要注意的有两点:
- 递归就是在过程或函数里面调用自身;
- 在使用递归时,必须有一个明确的递归结束条件,称为递归出口。
- 递归分为两个阶段:
- 递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
- 回归:当获得最简单的情况后,逐步返回,依次得到复杂的解。
int fib(int n)
{
if(0 == n)
return 0;
if(1 == n)
return 1;
if(n > 1)
return fib(n-1)+fib(n-2);
}
- 迭代:利用变量的原值推算出变量的一个新值。
- 如果递归是自己调用自己的话,迭代就是A不停的调用B;
- 对一组命令(或一定步骤)进行重复执行,在每次执行这组命令(或步骤)时,都从变量的原值退出它的一个新值。
- 利用迭代算法解决问题,需要做好以下三个方面的工作:
- 确定迭代变量:在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量;
- 建立迭代关系:所谓迭代关系,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决问题的关键,通常可以使用递推或倒推的方法来完成;
- 对迭代过程进行控制:在什么时候结束迭代过程。
- 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
- 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。
- 递归设计:
- 先写出一次执行函数;
- 再写母函数,按条件调用自己。
网友评论