文档章节

算法---->递归

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 1294
阅读 1
收藏 0

一、递归定义

递归(recursion)是指在定义自身的同时又出现了对自身的引用。如果一个算法直接或间接地调用自己,则称这个算法是一个递归算法。

任何一个有意义的递归算法总是由两部分组成:递归调用与递归终止条件

 

在实际应用中使用递归可以解决以下多方面的问题:

⑴  问题本身的定义就是递归的,例如许多数学定义就是递归的。

⑵  问题本身虽然不是递归定义的,但是它所用到的数据结构是递归的,例如链表、树就可以看成是递归定义的数据结构。

⑶ 问题的解法满足递归的性质,

二、递归与栈

⑴ 对调用函数的运行现场进行保护,主要是参数与返回地址等信息的保存;

⑵ 创建被调用函数的运行环境;

⑶ 将程序控制转移到被调用函数的入口。

在被调用函数执行结束之后,返回调用函数之前,系统同样需要完成3件工作:

⑴  保存被调函数的返回结果;

⑵  释放被调用函数的数据区;

⑶   依照保存的调用函数的返回地址将程序控制转移到调用函数。

 

递归方法在某些情况下却并不一定是最高效的方法,主要原因在于递归方法过于频繁的函数调用和参数传递,这会使系统有较大的开销。在某些情况下,若采用循环或递归算法的非递归实现,将会大大提高算法的实际执行效率。

三、例子

3.1、计算一个整数n的阶乘

3.2、计算以x为底的n次幂

3.3、输出n个布尔量的所有可能组合

public void coding(int[] b, int n) {
		if (n == 0) {
			b[n] = 0;
			outBn(b);
			b[n] = 1;
			outBn(b);
		}

		else {
			b[n] = 0;
			coding(b, n - 1);
			b[n] = 1;
			coding(b, n - 1);
		}
	}

	private void outBn(int[] b) {
		for (int i = 0; i < b.length; i++)
			System.out.print(b[i]);
		System.out.println();

	}

3.4汉诺塔问题

汉诺塔问题是由法国数学家Edouard Lucas 在1883 年发明的。n 阶汉诺塔问题可以描述为:假设有X、Y、Z 三个塔座,初始时有n 个大小不一的盘子按照从小到大的次序放在塔座X 上。现在要求将塔座X 上的所有盘子移动到塔座Z 上并保持原来的顺序,在移动过程中要满足以下要求:在塔座之间一次只能移动一个盘子并且任何时候大盘子都不能放到小盘子上。

                             

基本项:若只有一个盘子,则不需要使用过渡塔座,直接把它放到目的塔座即可。

递归项:如果多于一个盘子,则需要将塔座X 上的1 到n-1 个盘子使用Z 作为过渡塔座放到塔座Y 上,然后将第n 个盘子(最后一个盘子)放到塔座Z,最后将塔座Y 上的n-1个盘子使用塔座X 作为过渡放到塔座Z。

public void hanio(int n, char x, char y, char z) {

		if (n == 1)
			move(x, n, z);

		else {

			hanio(n - 1, x, z, y);
			move(x, n, z);
			hanio(n - 1, y, x, z);

		}

	}

	private void move(char x, int n, char y) {
		System.out.println("Move " + n + " from" + x + " to " + y);
	}

五、递推关系求解

5.1、数学归纳法

5.2、迭代法

5.3、线性齐次递推式的求解

  • 若q1,q2,…,qk为递归关系式的k个互不相同的特征根

  • 若递归关系的特征方程有一个m重根q,则qn,nqn,…,nm-1qn均为特征方程的解

以二阶为例

 

5.4、常系数线性非齐次递归关系的解法

只要求它的一个特解及导出的齐次递归关系的通解即可。对非齐线性递归关系的特解, 针对f(n)的特殊形式有以下情形:

 

5.5、Master Method(大致估计)

Master Method 为求解如下形式的递推式提供了简单的方法。

T(n) = aT(n/b) +f(n)

其中a、b为常数,并且a ≥ 1 , b > 1;f(n)是正的确定函数。

在Master Method 中分3 种不同的情况分别给出问题的解。T(n) = aT(n/b) +f(n) 是一类分治法的时间复杂性所满足的递归关系,即一个规模为n 的问题被分成规模均为n/b 的a 个子间题,递归地求解这a 个子问题,然后通过对这a 个子问题的解的综合,得到原问题的解。如果用T(n)表示规模为n 的原问题的复杂性,用f(n)表示把原问题分成a 个子问题和将a 个子问题的解综合为原问题的解所需要的时间,我们便有递推关系式T(n) = aT(n/b) +f(n) 。

T(n)渐近估计式

这里涉及的三类情况,都是拿f(n)与nlogba作比较。定理直观地告诉我们,递归关系式解的渐近阶由这两个函数中的较大者决定。

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/10/5637101.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
递归算法转非递归

将递归算法转换为非递归算法有两种方法,一种是直接求值,不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转...

u012557298
2017/12/01
0
0
递归算法经典实例小结(C#实现)

一 、递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。   递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问...

雲霏霏
2015/02/04
0
0
简单图像填充算法

填充算法 递归 private void fillsearch(Bitmap bmp, int x, int y, byte[,] flag,int num) { //向左 如果为1返回 如果不是1 计算当前值 如果不在范围内设为1返回 并且向下递归 if (Math.Abs...

魂祭心
2015/12/20
67
0
递归方法的非递归实现

递归是一种自顶向下的方法,直到方法知道如何解决最简单的问题,递归算法需要一个线性的空间开销,并且需要不断的压栈与出栈。一般来讲,非递归算法的资源开销比递归算法低。那么,我们如何实...

晨曦之光
2012/04/13
62
0
时间复杂度和空间复杂度的理解

一个算法的时间复杂度其实就是这个算法跑过的次数 eg: 这个算法执行的总次数f(n)=n^2 + 2*n; 简单来说时间复杂度就是这个函数执行的基本操作次数 你是不是会想时间复杂度为什么不用时间来衡...

triorwy
2017/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

angular 解决其他电脑不能访问的问题。

ng serve --host 0.0.0.0 --disable-host-check

miaojiangmin
今天
1
0
优酷视频文件怎么转换格式

  以前在优酷上下载视频都只是在手机上观看,但随着科技的发展,对于视频的要求也逐渐增多,不再只是观看视频那么简单,在精彩的部分还会将其单独分割出来,然后进行视频剪辑,可以做出我们...

萤火的萤火
今天
0
0
数据结构:散列

在一个数据结构中查找key元素,用顺序查找、二分查找都需要经过一系列关键之比较才能查找到结果,平均查找长度与数据量有关,元素越多比较次数就越多。 如果根据元素的关键字就能知道元素的存...

京一
今天
0
0
Apache RocketMQ 正式开源分布式事务消息

近日,Apache RocketMQ 社区正式发布4.3版本。此次发布不仅包括提升性能,减少内存使用等原有特性增强,还修复了部分社区提出的若干问题,更重要的是该版本开源了社区最为关心的分布式事务消...

阿里云云栖社区
今天
30
0
使用JavaScript和MQTT开发物联网应用

如果说Java和C#哪个是最好的开发语言,无疑会挑起程序员之间的相互怒怼,那如果说JavaScript是动态性最好的语言,相信大家都不会有太大的争议。随着越来越多的硬件平台和开发板开始支持JavaS...

少年不搬砖老大徒伤悲
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部