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

时间：2021-06-12 11:30:59

开心一笑

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

视频教程

大家好，我录制的视频《Java之优雅编程之道》已经在CSDN学院发布了，有兴趣的同学可以购买观看，相信大家一定会收获到很多知识的。谢谢大家的支持……

视频地址：http://edu.csdn.net/lecturer/994

提出问题

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);
        }
        return  0;
    }


}

结果：

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;
    }
}

树形结构数据如下：
Java算法之递归打破和在真实项目中的使用实例

重要的话讲三遍：

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

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

读书感悟

来自《风月俏佳人》

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

其他

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

相关文章