目录

文章目录

前言

一、递归的定义

二、递归的基本思想

三.递归的条件

四、递归的应用

1.汉诺塔问题

2.二分查找

3.斐波拉契数列的求值

前言

很多同学对于理解递归这种算法感到困惑，感觉有一种说不清，道不明的感觉，或许大多数初学者都会有这样的疑惑，但是递归算法在我们的生活中无时无刻不在体现，这种递归算法大抵就像一只纸糊的拦路虎，读者细细品味，便可理解。

提示：以下是本篇文章正文内容，下面案例可供参考

一、递归的定义

递归定义：若一个算法直接或间接地调用自己本身，则称这个算法是递归算法

二、递归的基本思想

在学习到阶乘时，常常会遇到计算某个数的阶乘，例如计算5！通常像下面会用循环去做

void jiechen()
{
	int x = 1;
	for (int i = 1; i <= 5; i++)
	{
		x = x * i;
	}
	printf("%d\n", x);
}

其实对于阶乘的问题用递归的思路依然可以

int main()
{
	printf("5的阶乘是%d", jiechen(5));
	return 0;
}
 
int jiechen(int n)
{
	if (n <= 1)
		return n;
	else
		return n * jiechen(n - 1);
}

通过对上面例子的举例，不难看出，递归无非就是不断地调用自己罢了，可以更加简单的理解为，在执行函数调用时，调用了一个跟自己长得一模一样的函数，功能也一样

 从这个问题中不难看出，阶乘所执行的只是简单重复的机械运动，那对于一个问题来说，什么时候我们会用到这种递归的方法呢? 

三.递归的条件

在递归的算法中，我们实际上解决的是将一个简单的运动重复n次的过程，是一个将一顿代码循环n次的过程，那为什么我们还要用这种算法呢？其实在后面数据结构的学习中，面对一些非线性结构时，我们的查找和遍历就需要这种方法。 对于一段重复的代码来说，其实还有一个问题我们应该注意，对于循环来说，我们需要有循环的条件，那对于递归，我们应该设置一个“出口”，要不然陷入到无限的调用自己中去，也是没有什么意义。

综上所述，递归的条件：

（1）简化后的问题与原问题有着相同的解决形式。

（2）递归必须有简洁的退出条件。

四、递归的应用

1.汉诺塔问题

解题思路：对于一个盘来说，我们只需将此盘从A移动到C上，对于两个盘子，我们需要先借助B，把第一个小的移动到B，再将第二个移动到C上，最后将第一个从B中移动到C中，对于n个盘子来说，可以将其看做是两个盘子，一个盘子是n，另外是由另外（n-1）个盘子所构成的一个盘子，那么移动的步骤如下：

1.将（n-1）个盘子从A移动到B上

2.将第n个盘子从A移动到C上

3.将（n-1）个盘子从B移动到C上

具体代码如下

void test01()
{
	printf("请输入现在有几个盘子:\n");
	int n;
	scanf_s("%d", &n);
	tower(n, 'A', 'C', 'B');
}
/*n 是盘子个数，frompeg是A，topeg是C,auxpegB*/
void tower(int n, char frompeg, char topeg, char auxpeg)
{
	if (n == 1)    /*设置递归出口*/
	{
		printf("%s%c%s%c\n", "move disk 1 from peg ", frompeg, " to peg ", topeg);
		return;
	}
	/*将（n-1）个盘子借助 C 从 A 移动到 B 上*/
	tower(n - 1, frompeg, auxpeg, topeg);
	/*将盘子n从 A 移动到 C 上*/
	printf("%s%d%s%c%s%c\n", "move disk ", n, " from peg ", frompeg, " to peg ", topeg);
	/*将（n-1）个盘子借助 A 从 B 移动到 C 上*/
	tower(n - 1, auxpeg, topeg, frompeg);
}

2.二分查找

解题思路：在一半的中去寻找另一半，直至找到为止

/*a[]数组a,x是查找的元素,low是查找的起点,high 是查找的终点*/
int chazhao(int a[], int x, int low, int high)
{
	int mid;
	mid = (high + low) / 2;      /*二分的中点*/
	if (a[mid] == x)
		return mid;
	else if (x < a[mid])        /*在二分中点的左边*/
	return chazhao(a, x, low, mid - 1);
else                        /*在二分中点的右边*/
    return chazhao(a, x, mid + 1, high);
}

3.斐波拉契数列的求值

解题思路：对于斐波拉契数列，很明显的特征就是从n>1开始，第三项等于前两项之和，也就是说，对于n=0,n=1来说是不满足递归的条件的，所以需要一点分类讨论

具体代码如下

void test03()
{
	int n;
	printf("请输入n的值是多少：\n");
	scanf_s("%d", &n);
	if(n<=1)
	{
		printf("n= %d 时值为 %d \n", n, n);
	}
	else
	   printf("n= %d 时值为 %d \n", n, jisuan(n-2,0,1,0));
}


/*n表示第n项的值 before是第前两项的值，after第前一项的值，current是现在的值*/
int jisuan(int n,int before,int after,int current)
{
	current = before + after;           /*前两项相加*/
	before = after;                     /*新的第前两项的值*/
	after = current;                    /*新的第前一项的值*/
	if (n == 0)
		return current;                 /*递归的条件是n==0，结果是返回current的值*/
	jisuan(n - 1, before, after, current);
	
}

总结

对于递归算法，最复杂的不是其过程，递归的过程只是简单的一个重复运动而已，而真正的关键在于我们是否能够在不同实际问题中抽象出这种思路！