递归和迭代

• 递归的基本概念：程序调用自身的编程技巧称为递归,是函数自己调用自己。
• 使用递归要注意的有两点：
  • 递归就是在过程或函数里面调用自身；
  • 在使用递归时,必须有一个明确的递归结束条件,称为递归出口。
• 递归分为两个阶段：
  • 递推：把复杂的问题的求解推到比原问题简单一些的问题的求解；
  • 回归：当获得最简单的情况后,逐步返回,依次得到复杂的解。

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；
  • 对一组命令（或一定步骤）进行重复执行，在每次执行这组命令（或步骤）时，都从变量的原值退出它的一个新值。
• 利用迭代算法解决问题，需要做好以下三个方面的工作：
  • 确定迭代变量：在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量；
  • 建立迭代关系：所谓迭代关系，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决问题的关键，通常可以使用递推或倒推的方法来完成；
  • 对迭代过程进行控制：在什么时候结束迭代过程。

• 递归中一定有迭代，但是迭代中不一定有递归，大部分可以相互转换。
• 能用迭代的不用递归，递归调用函数，浪费空间，并且递归太深容易造成堆栈的溢出。

• 递归设计：
  • 先写出一次执行函数；
  • 再写母函数，按条件调用自己。