文档章节

算法---->递归

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 1294
阅读 1
收藏 0
点赞 0
评论 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

递归算法经典实例小结(C#实现)

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

雲霏霏 ⋅ 2015/02/04 ⋅ 0

简单图像填充算法

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

魂祭心 ⋅ 2015/12/20 ⋅ 0

递归方法的非递归实现

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

晨曦之光 ⋅ 2012/04/13 ⋅ 0

时间复杂度和空间复杂度的理解

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

triorwy ⋅ 2017/12/09 ⋅ 0

python之递归

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

鹏爱 ⋅ 2017/07/17 ⋅ 0

java递归算法实现

Fibonacci数列:1,1,2,3,5,8,13…… public classFab { public static void main(String args[]){ } private static int fab(int index){ } } 程序分析: 这个实例是非常经典的实例,主......

动听的椰子 ⋅ 2016/03/01 ⋅ 0

python算法-1.简介/2.选择排序

第一章、 算法简介 一些常见的大O运行时间 》 ,也叫对数时间,这样的算法包括二分查找。 》 ,也叫线性时间,这样的算法包括简单查找。 》 ,这样的算法包括第4章将介绍的快速排序——一种速...

时间之友 ⋅ 2017/12/15 ⋅ 0

递归算法转换为非递归算法的技巧

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

fnqtyr45 ⋅ 2017/11/22 ⋅ 0

N个小球放进M个盒子算法

N个小球放入M个盒子共有多少种方法,并输出的算法设计: 算法思路1 :暴力填充盒子 每个小球都可能放入M个盒子的任意一个,所以直接根据小球个数做递归即可,然后将存储放入hash中排重 //TODO...

屌丝Lee ⋅ 2016/10/12 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 24分钟前 ⋅ 1

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部