Java算法之递归打破和在真实项目中的使用实例

2017-01-13 14:59:15来源:csdn作者:huangwenyi1010人点击

第七城市
开心一笑

刚才领导问开发:“你觉得这个项目的最大风险是什么”,开发说:”加班猝死” , 气氛尴尬了一分钟!!!

提出问题

1.递归算法简单复习 2.如何实现递归算法与真实项目接口??? 3.如何打破递归算法??? 简书地址:http://www.jianshu.com/users/d38a3668be58/latest_articles

解决问题

1.首先练习下网上一些递归经典题

package com.hwy.test;/**
* 递归函数测试
* Created by Ay on 2016/7/2.
*/
public class RecursionTest {public static void main(String[] args) {/** 利用递归函数实现1 + 2 + 3 ... 100**/
int sum = Sum(100);
System.out.println("the 1 + 2 + 3 ... 100 =" + sum);}/** 获得总和 **/
public static int Sum(int num){if(num > 0){
return num +Sum(num-1);
}
return0;
}
}

结果:

the 1 + 2 + 3 ... 100 =5050

2.求最大公约数

package com.hwy.test;/**
* 递归函数测试
* Created by Ay on 2016/7/2.
*/
public class RecursionTest {public static void main(String[] args) {
/** GCD最大公约数简称 **/
GCD(36,2);
}public static int GCD(int a,int b){if(a == b){
System.out.println("最大公约数为: " + a);
}else{
/** 用2个数相减的绝对值和和2个数的最小值一直比较,直到相等为止 **/
GCD(Math.abs(a -b),Math.min(a,b));
}
return 0;
}}

3.我们的重点不是这个,现在介绍在真实项目中的递归如何使用

业务场景是这样的:从数据库中查询一颗树,我现在用代码模拟,具体可看下面的代码,我们要做的是遍历该树,如果该树中的节点id等于我们传入的id,终止遍历该树。

package com.hwy.test;import com.alibaba.fastjson.JSONObject;
import org.apache.commons.lang3.StringUtils;
import java.util.ArrayList;
import java.util.List;/**
* 节点
*/
class Node{/** 节点id **/
private String id;
/** 父节点id **/
private String pid;
/** 节点名称 **/
private String name;
/** 子节点 **/
private List<Node> childen;
/** 构造函数 **/
public Node(){}
/** 构造函数 **/
public Node(String id,String pid,String name,List<Node> nodes){
this.id = id;
this.pid = pid;
this.name = name;
this.childen = nodes;
}public String getId() {
return id;
}public void setId(String id) {
this.id = id;
}public String getPid() {
return pid;
}public void setPid(String pid) {
this.pid = pid;
}public String getName() {
return name;
}public void setName(String name) {
this.name = name;
}public List<Node> getChilden() {
return childen;
}public void setChilden(List<Node> childen) {
this.childen = childen;
}
}/**
* 递归函数测试
* Created by Ay on 2016/7/2.
*/
public class RecursionTest {public static String nodeName = "";public static void main(String[] args) {
/** 初始化树模型 **/
Node node = initTreeModel();
/** 节点id **/
getNodeId(node, "CC2");
}/**
*
* @param node
* @return
*/
public static String getNodeId(Node node,String myId){
/** 打印每次遍历节点信息 **/
System.out.println("--->>>" + node.getId());
/** 判断是否是我们苦苦寻找的id **/
if(StringUtils.isNotEmpty(myId) && myId.equals(node.getId())){
nodeName = node.getName();
return nodeName;
}else{
if(null != node.getChilden() && node.getChilden().size() >0){
for(Node n:node.getChilden()){
/** 这里是重点中的重点,如果nodeName不为空,恭喜你找到了,返回该值,
递归函数就会一层一层的返回,每一层的返回都会进行该判断,但我们已经找到
值了,所有递归相当于被打破了**/
if(StringUtils.isNotEmpty(nodeName)){
return nodeName;
}else{
/** 继续递归 **/
getNodeId(n, myId);
}}
}
return null;
}
}
/**
* 初始化树模型
* @return
*/
public static Node initTreeModel(){
/** 构造第三层节点 **/
Node AAA1 = new Node("AAA1","AA1","AAA1",null);
Node AAA2 = new Node("AAA2","AA1","AAA2",null);
Node AAA3 = new Node("AAA3","AA1","AAA3",null);
Node AAA4 = new Node("AAA4","AA1","AAA4",null);
List<Node> AAANodes = new ArrayList<>();
AAANodes.add(AAA1);
AAANodes.add(AAA2);
AAANodes.add(AAA3);
AAANodes.add(AAA4);Node AA1 = new Node("AA1","A","AA1",null);
Node AA2 = new Node("AA2","A","AA2",null);
Node AA3 = new Node("AA3","A","AA3",null);List<Node> AANodes = new ArrayList<>();
AANodes.add(AA1);
AANodes.add(AA2);
AANodes.add(AA3);Node A = new Node("A","0","A",null);AA1.setChilden(AAANodes);
A.setChilden(AANodes);Node BBB1 = new Node("BBB1","BB1","BBB1",null);
Node BBB2 = new Node("BBB2","BB1","BBB2",null);
Node BBB3 = new Node("BBB3","BB1","BBB3",null);
Node BBB4 = new Node("BBB4","BB1","BBB4",null);List<Node> BBBNode = new ArrayList<>();
BBBNode.add(BBB1);
BBBNode.add(BBB2);
BBBNode.add(BBB3);BBBNode.add(BBB4);Node BB1 = new Node("BB1","B","BB1",null);
Node BB2 = new Node("BB2","B","BB2",null);
Node BB3 = new Node("BB3","B","BB3",null);List<Node> BBNode = new ArrayList<>();
BBNode.add(BB1);
BBNode.add(BB2);
BBNode.add(BB3);Node B = new Node("B","0","B",null);B.setChilden(BBNode);
BB1.setChilden(BBBNode);Node CC1 = new Node("CC1","C","CC1",null);
Node CC2 = new Node("CC2","C","CC2",null);
Node CC3 = new Node("CC3","C","CC3",null);
List<Node> CCNode = new ArrayList<>();
CCNode.add(CC1);
CCNode.add(CC2);
CCNode.add(CC3);Node C = new Node("C","0","C",null);
C.setChilden(CCNode);List<Node> nodes = new ArrayList<>();
nodes.add(A);
nodes.add(B);
nodes.add(C);Node root = new Node("0",null,"root",nodes);
/** 打印json数据 **/
System.out.println(JSONObject.toJSON(root).toString());
return root;
}
}

树形结构数据如下: 树形结构数据

重要的话讲三遍:

这里是重点中的重点,如果nodeName不为空,恭喜你找到了,返回该值,递归函数就会一层一层的返回,每一层的返回都会进行该判断,但我们已经找到值了,所有递归相当于被打破了

这里是重点中的重点,如果nodeName不为空,恭喜你找到了,返回该值,递归函数就会一层一层的返回,每一层的返回都会进行该判断,但我们已经找到值了,所有递归相当于被打破了

读书感悟

来自《风月俏佳人》


维维安: 小时候,当我做错事的时候,我妈妈经常把我关在楼阁里。然后我就会感觉自己是一个被恶毒的女王囚禁的公主。总相信会有一个骑士突然出现,手里挥舞着剑,骑着白马上来,把我从楼阁中营救出来……但一直没有出现,每次幻想中,骑士确实对我说,“来吧,亲爱的,我会把你带入一座雄伟的华厦。”
放弃这么美好的东西一定很困难
其他

如果有带给你一丝丝小快乐,就让快乐继续传递下去,欢迎转载,点赞,顶,欢迎留下宝贵的意见,多谢支持!


第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台