本文共 1524 字，大约阅读时间需要 5 分钟。

一、递归基本知识

1、递归：指直接或间接的不断调用自身

2、函数调用自身的具体过程如下：

【注】：函数调用自身和调用其它的函数在计算机上是没有任何区别的。

3、递归需要满足如下三个条件

• 递归必须要有一个明确的中止条件
• 该函数所处理的数据规模必须是在递减
• 这个转化必须是可解的

4、循环和递归的区别

（1）、递归：

• 易于理解
• 速度慢
• 存储空间大（浪费大量的存储空间）

（2）、循环

• 速度快
• 存储空间小（几乎不浪费存储空间）
• 可以用循环的都可以用递归来解决，但可以用递归的不一定可以用循环

二、递归的应用实例

1、累加和阶乘的递归算法

#include
   
    using namespace std;// 累加：1+2+3+4+5+...........int TheAdd(int num){	int sum = 0;	if (num==1)	{		return 1;	}	else	{		sum = num + TheAdd(num - 1);	}	return sum;}// 阶乘int TheFactorial(int num){	int s1 = 0;	if (num == 0 || num == 1)	{		s1 = 1;	}	else	{		s1 = num * TheFactorial(num - 1);	}	return s1;}int main(){	cout << "100 的累加和是：\n" << TheAdd(100) << endl;	cout << "6的阶乘是：\n" << TheFactorial(6) << endl;	cin.get();}
   

结果如下图

2、汉诺塔的递归算法

（1）、伪算法

if ( n > 1 ){    先把A上的前n-1个盘子从A借助C移动到B上；    再把A上的第n个盘子直接移动到C上；    把B上的 n-1 个盘子借助 A 移动到C上；}

（2）、对应的代码如下

参数 A表示方盘子的柱子，B 表示借助的柱子，C 表示要盘子最终要移动到的柱子

#include
   
    using namespace std;// 参数的含义：n 表示盘子的个数，初始化时都在A上；// A、B、C的参数是 A借助B将盘子移动到C上void HanNuoT(int  n,char A,char B,char C){	if (n==1)	{		// 如果只有一个盘子时,直接将盘子从A柱子移动到C柱子		cout << "将编号为 " << n << " 的盘子直接从 " << A << " 柱子移动到 " << C << " 柱子" << endl;	}	else	{		// 当盘子数量大于1个时,先将A上的n-1个盘子借助C移动到B上。		// 此时A上只有第n个盘子，B上有n-1个盘子		HanNuoT(n - 1, A, C, B);		// 然后将A上的第n个盘子直接移动到C上。		// 此时A上为空，B上有n-1个盘子，C上为第n个盘子		cout << "将编号为 " << n << " 的盘子直接从 " << A << " 柱子移动到 " << C << " 柱子" << endl;		// 再让B借助A，将剩下的 n-1 个盘子移动到C上，同样调用递归函数来执行		HanNuoT(n - 1, B, A, C);	}}int main(){	int num;	cout << "请输入n的值：";	cin >> num;	HanNuoT(num, 'X', 'Y', 'Z');	system("pause");}
   

运行结果如下

转载地址：http://tsegf.baihongyu.com/