文档章节

算法---->递归

小强斋太
 小强斋太
发布于 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
时间复杂度和空间复杂度的理解

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

triorwy
2017/12/09
0
0
python之递归

递归 特点: 递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点:...

鹏爱
2017/07/17
0
0
递归算法转换为非递归算法的技巧

递归函数具有很好的可读性和可维护性,但是大部分情况下程序效率不如非递归函数,所以在程序设计中一般喜欢先用递归解决问题,在保证方法正确的前提下再转换为非递归函数以提高效率。 函数调...

fnqtyr45
2017/11/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Libusb交叉编译和移植

  Libusb交叉编译和移植      某项目内核需要支持USB的相关操作,所以考虑移植Libusb库      1、到官网下载最新的libusb源码(1.0.22)      2、解压源码      3、进入解压...

SEOwhywhy
10分钟前
1
0
阿里云HBase全新发布X-Pack NoSQL数据库再上新台阶

一、八年双十一,造就国内最大最专业HBase技术团队 阿里巴巴集团早在2010开始研究并把HBase投入生产环境使用,从最初的淘宝历史交易记录,到蚂蚁安全风控数据存储。持续8年的投入,历经8年双...

阿里云云栖社区
13分钟前
1
0
【58沈剑 架构师之路】数据库索引,到底是什么做的?

问题1. 数据库为什么要设计索引? 图书馆存了1000W本图书,要从中找到《架构师之路》,一本本查,要查到什么时候去? 于是,图书管理员设计了一套规则: (1)一楼放历史类,二楼放文学类,三楼...

张锦飞
14分钟前
1
0
android webpage err_unknown_url_scheme

搞一个 Android 的webview demo 来访问网页, 结果 模拟器就报错了: webpage err_unknown_url_scheme 于是去百度了 一下。发现挺多解决方案的,都拿来试试。居然有几种方式都可以。 1, 参考...

之渊
16分钟前
1
0
JVM总结

区域简介 JVM运行时区域有些随着虚拟机进程的启动而存在,有些依赖于用户线程的启动和结束而建立和销毁,大致分为以下几类:方法区,虚拟机栈,本地方法栈,堆,程序计数器,概念图如下(源于...

瑞查德-Jack
17分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部