递归算法的简单解析

2021/10/16 17:12:18

本文主要是介绍递归算法的简单解析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

文章目录

前言

一、递归的定义

二、递归的基本思想

三.递归的条件

四、递归的应用

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);
	
}

总结

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



这篇关于递归算法的简单解析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程