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

开心一笑

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

提出问题

1.递归算法简单复习 2.如何实现递归算法与真实项目接口？？？ 3.如何打破递归算法？？？

解决问题

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

 1 package com.hwy.test;
 2 
 3 /**
 4  * 递归函数测试
 5  * Created by Ay on 2016/7/2.
 6  */
 7 public class RecursionTest {
 8 
 9     public static void main(String[] args) {
10 
11         /** 利用递归函数实现1 + 2 + 3 ... 100  **/
12         int sum = Sum(100);
13         System.out.println("the 1 + 2 + 3 ... 100 =" + sum);
14 
15     }
16 
17     /** 获得总和 **/
18     public static int Sum(int num){
19 
20         if(num > 0){
21             return num +Sum(num-1);
22         }
23         return  0;
24     }
25 
26 
27 }

结果：

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

2.求最大公约数

 1 package com.hwy.test;
 2 
 3 /**
 4  * 递归函数测试
 5  * Created by Ay on 2016/7/2.
 6  */
 7 public class RecursionTest {
 8 
 9     public static void main(String[] args) {
10         /** GCD最大公约数简称 **/
11         GCD(36,2);
12     }
13 
14     public static int GCD(int a,int b){
15 
16         if(a == b){
17             System.out.println("最大公约数为: " + a);
18         }else{
19             /** 用2个数相减的绝对值和和2个数的最小值一直比较，直到相等为止 **/
20             GCD(Math.abs(a -b),Math.min(a,b));
21         }
22         return 0;
23     }
24 
25 }

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

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

  1 package com.hwy.test;
  2 
  3 import com.alibaba.fastjson.JSONObject;
  4 import org.apache.commons.lang3.StringUtils;
  5 import java.util.ArrayList;
  6 import java.util.List;
  7 
  8 /**
  9  * 节点
 10  */
 11 class Node{
 12 
 13     /** 节点id **/
 14     private String id;
 15     /** 父节点id **/
 16     private String pid;
 17     /** 节点名称 **/
 18     private String name;
 19     /** 子节点 **/
 20     private List<Node> childen;
 21     /** 构造函数 **/
 22     public Node(){}
 23     /** 构造函数 **/
 24     public Node(String id,String pid,String name,List<Node> nodes){
 25         this.id = id;
 26         this.pid = pid;
 27         this.name = name;
 28         this.childen = nodes;
 29     }
 30 
 31     public String getId() {
 32         return id;
 33     }
 34 
 35     public void setId(String id) {
 36         this.id = id;
 37     }
 38 
 39     public String getPid() {
 40         return pid;
 41     }
 42 
 43     public void setPid(String pid) {
 44         this.pid = pid;
 45     }
 46 
 47     public String getName() {
 48         return name;
 49     }
 50 
 51     public void setName(String name) {
 52         this.name = name;
 53     }
 54 
 55     public List<Node> getChilden() {
 56         return childen;
 57     }
 58 
 59     public void setChilden(List<Node> childen) {
 60         this.childen = childen;
 61     }
 62 }
 63 
 64 /**
 65  * 递归函数测试
 66  * Created by Ay on 2016/7/2.
 67  */
 68 public class RecursionTest {
 69 
 70     public static String nodeName = "";
 71 
 72     public static void main(String[] args) {
 73         /** 初始化树模型 **/
 74         Node node = initTreeModel();
 75         /** 节点id **/
 76         getNodeId(node, "CC2");
 77     }
 78 
 79     /**
 80      *
 81      * @param node
 82      * @return
 83      */
 84     public static String getNodeId(Node node,String myId){
 85         /** 打印每次遍历节点信息 **/
 86         System.out.println("--->>>" + node.getId());
 87         /** 判断是否是我们苦苦寻找的id **/
 88         if(StringUtils.isNotEmpty(myId) && myId.equals(node.getId())){
 89             nodeName = node.getName();
 90             return nodeName;
 91         }else{
 92             if(null != node.getChilden() && node.getChilden().size() >0){
 93                     for(Node n:node.getChilden()){
 94                         /** 这里是重点中的重点，如果nodeName不为空，恭喜你找到了，返回该值,
 95                           递归函数就会一层一层的返回，每一层的返回都会进行该判断，但我们已经找到
 96                          值了，所有递归相当于被打破了**/
 97                         if(StringUtils.isNotEmpty(nodeName)){
 98                             return nodeName;
 99                         }else{
100                             /** 继续递归 **/
101                             getNodeId(n, myId);
102                         }
103 
104                     }
105             }
106             return null;
107         }
108     }
109 
110 
111     /**
112      * 初始化树模型
113      * @return
114      */
115     public static Node initTreeModel(){
116         /** 构造第三层节点 **/
117         Node AAA1 = new Node("AAA1","AA1","AAA1",null);
118         Node AAA2 = new Node("AAA2","AA1","AAA2",null);
119         Node AAA3 = new Node("AAA3","AA1","AAA3",null);
120         Node AAA4 = new Node("AAA4","AA1","AAA4",null);
121         List<Node> AAANodes = new ArrayList<>();
122         AAANodes.add(AAA1);
123         AAANodes.add(AAA2);
124         AAANodes.add(AAA3);
125         AAANodes.add(AAA4);
126 
127         Node AA1 = new Node("AA1","A","AA1",null);
128         Node AA2 = new Node("AA2","A","AA2",null);
129         Node AA3 = new Node("AA3","A","AA3",null);
130 
131         List<Node> AANodes = new ArrayList<>();
132         AANodes.add(AA1);
133         AANodes.add(AA2);
134         AANodes.add(AA3);
135 
136         Node A = new Node("A","0","A",null);
137 
138         AA1.setChilden(AAANodes);
139         A.setChilden(AANodes);
140 
141         Node BBB1 = new Node("BBB1","BB1","BBB1",null);
142         Node BBB2 = new Node("BBB2","BB1","BBB2",null);
143         Node BBB3 = new Node("BBB3","BB1","BBB3",null);
144         Node BBB4 = new Node("BBB4","BB1","BBB4",null);
145 
146         List<Node> BBBNode = new ArrayList<>();
147         BBBNode.add(BBB1);
148         BBBNode.add(BBB2);
149         BBBNode.add(BBB3);
150 
151         BBBNode.add(BBB4);
152 
153         Node BB1 = new Node("BB1","B","BB1",null);
154         Node BB2 = new Node("BB2","B","BB2",null);
155         Node BB3 = new Node("BB3","B","BB3",null);
156 
157         List<Node> BBNode = new ArrayList<>();
158         BBNode.add(BB1);
159         BBNode.add(BB2);
160         BBNode.add(BB3);
161 
162         Node B = new Node("B","0","B",null);
163 
164         B.setChilden(BBNode);
165         BB1.setChilden(BBBNode);
166 
167         Node CC1 = new Node("CC1","C","CC1",null);
168         Node CC2 = new Node("CC2","C","CC2",null);
169         Node CC3 = new Node("CC3","C","CC3",null);
170         List<Node> CCNode = new ArrayList<>();
171         CCNode.add(CC1);
172         CCNode.add(CC2);
173         CCNode.add(CC3);
174 
175         Node C = new Node("C","0","C",null);
176         C.setChilden(CCNode);
177 
178         List<Node> nodes = new ArrayList<>();
179         nodes.add(A);
180         nodes.add(B);
181         nodes.add(C);
182 
183         Node root = new Node("0",null,"root",nodes);
184         /** 打印json数据 **/
185         System.out.println(JSONObject.toJSON(root).toString());
186         return root;
187     }
188 }

树形结构数据如下：

树形结构数据

重要的话讲三遍：

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

读书感悟

来自《风月俏佳人》

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

其他

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