#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)
blank

相关推荐

  • 捷达vs7与VS5是一个平台打造_visual studio没有控制台应用程序

    捷达vs7与VS5是一个平台打造_visual studio没有控制台应用程序我正在使用VisualStudioTeamServices(是VSOnline)。我从VisualStudio2013升级到了VisualStudio2015。当我打开源代码管理项目时,出现以下错误:您已加载的解决方案已绑定到https://xx.visualstudio.com/defaultcollection上的源控制服务器,但该服务器上没有任何工作空间可以找到服务器。如果您确…

  • Macbook上打开多个终端的方法[通俗易懂]

    Macbook上打开多个终端的方法

  • Repeater控件的ItemDataBound事件

    Repeater控件的ItemDataBound事件Repeater控件的ItemDataBound事件:在项被绑定数据后触发。下面的例子来自msdn,不过我把前台和后台分开了。前台是:ViewCode<%@PageLanguage="C#"AutoEventWireup="true"CodeBehind="WebForm1.aspx.cs"Inherits="WebApplication2.WebForm1…

    2022年10月13日
  • 字节、字、bit、byte的关系

    字节、字、bit、byte的关系字word字节byte位bit,来自英文bit,音译为“比特”,表示二进制位。字长是指字的长度1字=2字节(1word=2byte)1字节=8位(1byte=8bit)一个字的字长为16一个字节的字长是8bps是bitspersecond的简称。一般数据机及网络通讯的传输速率都是以「bps」为单位。如56Kbps、100.0Mbps等等。B…

  • iot技术_如何帮助阿尔兹海默症

    iot技术_如何帮助阿尔兹海默症场景介绍阿尔茨海默病,是导致中老年人认知功能障碍的最常见疾病之一,是发生在老年期及老年前期的一种原发性退行性脑病。据估计,全世界痴呆症患者数量为4700万,到2030年将达到7500万人。痴呆症患者数量到2050年预计将是现在的近三倍。疾病的高昂费用给卫生系统应对未来预计不断增加的病例构成挑战。据估计,目前每年的支出为8180亿美元,而支出的增长速度预计会比疾病流行率上升还要快。照料痴呆症患者…

  • MAVEN使用说明

    MAVEN使用说明

发表回复

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

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