#Java算法设计与分析1–递归算法

#Java算法设计与分析1–递归算法1.递归算法1.1递归的概念所谓递归,就是程序方法在运行过程中自身调用自身。定义如下所示。fn(){ if(递归出口条件){ returnx;}else{ //somecodes…returnfn();}}1.2递归的使用条件1.2.1必须要有明确的递归出口所谓递归出口就是需要有明确的结束条件。1.2.2每次递归都要使问题的规模减小1.2.3递归的规模…

大家好,又见面了,我是你们的朋友全栈君。

1.递归算法
1.1递归的概念
所谓递归,就是程序方法在运行过程中自身调用自身。定义如下所示。

fn(){
	if(递归出口条件){
		return x;
}else{
	//some codes…
return fn();
}
}

1.2递归的使用条件
1.2.1 必须要有明确的递归出口
所谓递归出口就是需要有明确的结束条件。
1.2.2 每次递归都要使问题的规模减小
1.2.3 递归的规模不能太大
如果递归次数太多,很容易造成内存泄露。

1.3递归的优点及缺点
递归是一种算法策略。在二叉树、广义链表的节点遍历情景中,具有很重要的价值。事实上,递归与循环是解决遍历数据问题的两种不同的思路。对于循环而言,效率高是它的一大显著特点,不会占用额外的内存开销,但也有缺点,使用循环写的代码可读性不强,而且代码往往冗长;对于递归而言,效率方面较循环要逊色一些,因为递归需要开辟额外的内存空间,但优点是其代码简洁清爽,较为严谨,在解决某些特殊问题,又不得不使用递归来求解。一般地,递归问题都能转换为循环进行求解。

1.4递归举例
1.4.1 字符串反向输出
描述:输入字符串abc,要求能输出cba,以此类推。
分析:我们可以这样来考虑这个问题,cba=c+ba,这样,这个问题的规模就化解为了一个字母与ba这个字符串进行拼接,也就是f(3) = c+f(2)=cb+f(1),每递归一次,数组长度就减1,直到数组长度为0时,就是递归出口。代码如下所示。

package com.yzh.maven.main;
public class Digui {
	static int length = 0;
	public static void main(String[] args) {
		System.out.println(reverse("abcsdfg".toCharArray()));
	}
	
	public static String reverse(char[] c){
		length = c.length;
		String obj = "";
		//递归出口
	      if(length == 0){
			return obj;
		}else{
			//获取当前元素
			obj = c[--length]+"";
			//定义中间数组
			char[] c1 = new char[length];
//变为长度-1,问题规模减小
			System.arraycopy(c,0,c1,0,length);
			return obj+reverse(c1);
		}
	}
}

1.4.2 斐波纳契数列问题
描述:求1,1,2,3,5,8,13…数列的第n项。
分析:我们注意到,该数列从第三项开始,其数值等于前两项之和。这个表达式可以用fn(n) = fn(n-1)+fn(n-2) (n>2)来表示。当n=1或n=2时,可以直接获取结果,因此可以作为递归的出口;而fn(n-1) = fn(n-2)+fn(n-3),我们看到,该问题再向出口一步步靠近,也就是问题规模在不断减小,因此满足递归的条件。代码实现如下所示。

public static int fibonacci(int n){
	//递归出口
	if(n == 1 || n == 2){
		return 1;
	}else{
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

1.4.3阶乘问题
描述:求n!。
分析:对于阶乘,我们同样可以使用递归求解。我们令fn(n)=!n,那么fn(n-1)=(n-1)!,从而fn(n)=nfn(n-1),当n=1时,那么fn(1)=10!=1,能够直接获得的结果可以作为递归出口,同时,我们看到阶乘的规模在一步步减小,直到直接获得作为递归出口的结果。代码如下所示。

public static int factorial(int n){
	//递归出口
if(n == 1){
		return 1;
	}else{
		return n*factorial(n-1);
	}
}

1.4.4单链表节点数据的遍历
在这里插入图片描述
分析:我们知道,单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息(需要存储的数据),另一个部分存储下一个节点的地址,也就是指针域。最后一个节点存储地址的部分指向空值。我们可以利用这个空值来作为单链表节点数据的遍历的递归出口,代码如下所示。
节点模型:

package com.yzh.maven.main;

public class Node {
	private Object data;
	private Node nextNode;
	public Object getData() {
		return data;
	}
	public void setData(Object data) {
		this.data = data;
	}
	public Node getNextNode() {
		return nextNode;
	}
	public void setNextNode(Node nextNode) {
		this.nextNode = nextNode;
	}
}

取出所有的节点数据:
public static void showAllNodeData(Node node){
	//递归出口
	if(null == node){
		return;
	}else{
		System.out.print(node.getData()+"->");
		showAllNodeData(node.getNextNode());
	}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/156720.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Vue、Element-ui项目中如何使用Iconfont(阿里图标库)[通俗易懂]

    Vue、Element-ui项目中如何使用Iconfont(阿里图标库)[通俗易懂]我们使用element-ui、vue开发网站的时候,往往图标是起着很重要的作用。2018-11-9更新1.傻瓜式引用:由于这种方法及其简单省去了很多繁琐的步骤,a.引入项目生成的,图标地址。b.使用推荐使用这种,详情请看文档!!文档够详细的了。http://www.iconfont.cn/help/detail?spm=a313x.7781069.1998910419.d8cf4…

  • DataGrid的多行提交

    DataGrid的多行提交

  • pycharm2021激活码10月_在线激活[通俗易懂]

    (pycharm2021激活码10月)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 数据库系统概论课后习题答案(第五版 王珊、萨师煊)

    数据库系统概论课后习题答案(第五版 王珊、萨师煊)第1章绪论1.试述数据、数据库、数据库系统、数据库管理系统的概念。答:(l)数据(Data):描述事物的符号记录称为数据。数据的种类有数字、文字、图形、图像、声音、正文等。数据与其语义是不可分的。解析在现代计算机系统中数据的概念是广义的。早期的计算机系统主要用于科学计算,处理的数据是整数、实数、浮点数等传统数学中的数据。现代计算机能存储和处理的对象十分广泛,表

    2022年10月26日
  • DTW和DBA_电台文本

    DTW和DBA_电台文本DTW(动态时间调整)动态时间调整算法是大多用于检测两条语音的相似程度,由于每次发言,每个字母发音的长短不同,会导致两条语音不会完全的吻合,动态时间调整算法,会对语音进行拉伸或者压缩,使得它们竟可能

  • netperf 而网络性能测量

    netperf 而网络性能测量

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号