递归与迭代的联系以及优缺点（以c++为例）

1.递归的定义：

程序直接或间接的调用自身的方法。

递归算法的特点：

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

递归算法的代码，可以分成两个部分：递归部分包括递归代码的主体和递归出口（需要满足的输出条件）。把整体运算转换为分步运算。

案例：汉诺塔

这个例子可以用递归算法实现。

ABC分别是123柱子，代码思路大概是这样的

把N-1层的环子先通过C移到B，最后再把第N层的最大的环子移到C，这个时候就剩下一个N-1层的新“塔”，那么我们把他看成一个新的“塔”把B柱看成之前的A柱，通过C柱把（N-1）-1层移到A柱，再把第N-1层的最大（原本第二大）的环子放到C，如此循环到最后的N=1 。

实现方法：

 1 #include<iostream>
 2 using namespace std;
 3 void hanoi(int n,char a,char b,char c)
 4 {
 5　　 if(n==1)
 6 　　cout<<n<<" "<<a<<" "<<c<<endl;
 7　　 else
 8 　　{
 9 　　　　hanoi(n-1,a,c,b);
10 　　　　cout<<n<<" "<<a<<" "<<c<<endl;
11 　　　　hanoi(n-1,b,a,c);
12 　　}
13 }
14 int main()
15 {
16 　　int n;
17　　 cout<<"输入正整数:"<<endl;
18　　 cin>>n;
19　　 cout<<"结果为"<<endl;
20　　 hanoi(n,'A','B','C');
21 
22 
23 　　return 0;
24 } 

2.分析：

从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛时，才可采用递归算法，否则，就不能使用递归算法。

递归的优点：

1）大问题化为小问题,可以极大的减少代码量；

2）用有限的语句来定义对象的无限集合.；

3）代码更简洁清晰，可读性更好

递归的缺点

1）递归调用函数,浪费空间；

2）递归太深容易造成堆栈的溢出；

迭代的优点：

1）迭代效率高，运行时间只因循环次数增加而增加；

2）没什么额外开销，空间上也没有什么增加，

迭代的缺点：

1） 不容易理解；

2） 代码不如递归简洁；

3） 编写复杂问题时困难。

3.两者之间的关系

1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。

2） 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。