递归和迭代小结
迭代是人，递归是神。递归和迭代都是循环的一种。总结分析递归和迭代的区别、联系、优缺点及实例分析。
一、相关概念
递归
递归（recursion）在计算机科学中是指一种通过重复将问题分解为同类问题的子问题而解决问题的方法。可以极大地减少代码量。递归的能力在于用有限的语句来定义对象的无限集合。
递归是设计和描述算法的一种有力的工具，能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
使用递归要注意的有两点：
1）递归就是在过程或函数里调用自身；
2）在使用递归时，必须有一个明确的递归结束条件，称为递归出口。
递归分为两个阶段：
1）递推：把复杂的问题的求解推到比原问题简单一些的问题的求解；
2）回归：当获得最简单的情况后，逐步返回，依次得到发杂的解。
利用递归可以解决很多问题:如背包问题,汉诺塔问题,斐波那契数,...等.
优点：
1）大问题化为小问题,可以极大的减少代码量；
2）用有限的语句来定义对象的无限集合.；
3）代码更简洁清晰，可读性更好
缺点：
1）递归调用函数,浪费空间；
2）递归太深容易造成堆栈的溢出；
迭代
迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。迭代大部分时候需要人为的对问题进行剖析，将问题转变为一次次的迭代来逼近答案。
迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快，适合做重复性操作的特点，让计算机对一组命令（或一定步骤）进行重复执行，在每次执行这组命令（或步骤）时，都从变量的原值退出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作：
（1）确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
（2）建立迭代关系。所谓迭代关系，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决问题的关键，通常可以使用递推或倒推的方法来完成。
（3）对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
优点：
1）迭代效率高，运行时间只因循环次数增加而增加；
2）没什么额外开销，空间上也没有什么增加。
缺点：
1） 不容易理解；
2） 代码不如递归简洁；
3） 编写复杂问题时困难。
递归和迭代的比较
相同点：
递归和迭代都是循环的一种。
不同点：
1、程序结构不同
递归是重复调用函数自身实现循环。
迭代是函数内某段代码实现循环。
其中，迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
2、算法结束方式不同
递归循环中，遇到满足终止条件的情况时逐层返回来结束。
迭代则使用计数器结束循环。
当然很多情况都是多种循环混合采用，这要根据具体需求。
3、效率不同
在循环的次数较大的时候，迭代的效率明显高于递归。
二者联系：
1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
2） 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.（具体情况具体分析）
实例分析
以斐波那契数列的求解为例：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1) fib(n-2);
递归实现：
代码语言：javascript复制int fab_recursion(int n){
if(n>1) return fib(n-1) fib(n-2);
else return n; //n = 0,1时给出递归终止条件
}迭代实现：
代码语言：javascript复制//迭代实现斐波那契数列
int fab_iteration(int n)
{
if(n<=1)
{
return n;
}
else
{
int f0 = 0;
int f1 = 1;
int f2;
for(int i = 2; i <= n; i )
{
f2 = f0 f1; //利用变量的原值推算出变量的一个新值
f0 = f1;
f1 = f2;
}
return f2;
}
}
