【递归】java递归算法及替代方法

超、凢脫俗 2024-04-01 16:42 94阅读 0赞

#### 文章目录 ####

*  菜单树递归（树根往子节点递归）
 *   *   *  需求： 取所有level小于2的节点 ( 返回结果为普通list格式)
 *  为list格式的数据设置children（非递归）
 *   *   *  需求： 数据库查出来的原始list 如果有children就设置
 *  使用循环代替向下递归
 *   *   *  需求：使用循环的方式 代替菜单树的递归

递归会造成压栈 栈帧变多 容易Stack Overflow，所以递归一般用于有限且数量可控范围内

个人是很讨厌递归的，一般要用到递归的实际场景，代码就是又臭又长了，但这也是最简单粗暴的算法了，所以记录个工作中遇到的递归案例，平常也需要加强练习，遇到才不会不知所措。

## 菜单树递归（树根往子节点递归） ##

#### 需求： 取所有level小于2的节点 ( 返回结果为普通list格式) ####

Tree结构

private Long id;
        private Long fid;
        private Integer level;
        private List<Tree> children;

allTreeList数据：  
![在这里插入图片描述][0523a099c213402085a09dafc2035d35.jpeg]

代码实现：

// SysMenuDTO 继承Tree
     List<SysMenuDTO> res= new ArrayList<>();
     res= handleChild(allTreeList, res);

handleChild 方法：

private List<SysMenuDTO> handleChild(List<SysMenuDTO> treeList, List<SysMenuDTO> resList) {
        
    
            for (SysMenuDTO each : treeList) {
        
                if (each.getLevel() < 2) {
        
                    resList.add(each);
                }
                if (null != each.getChildren()) {
        
                    List<Tree> children = each.getChildren();
                    // 转型
                    List<SysMenuDTO> treeChild = new ArrayList<>();
                    for (Tree child : children) {
        
                        treeChild.add((SysMenuDTO) child);
                    }
                    handleChild(treeChild, resList);
                }
            }
            return resList;
        }

## 为list格式的数据设置children（非递归） ##

#### 需求： 数据库查出来的原始list 如果有children就设置 ####

Tree结构同上

list数据： 可以看到此时的数据是平铺的 children为null  
![在这里插入图片描述][cd9ce0b540474f1fb7c3612aae423e42.png]  
代码实现：

// allTreeList 结构同上
    List<SysMenuDTO> allTreeList = Tree.assembleTree(allList);

public static <T extends Tree> List<T> assembleTree (List<T> vos) {
        
    
            /*如果节点数为0或1，则不需要组装*/
            if ( vos == null ) {
        
                return vos;
            }
    
            List<T> retList = new ArrayList<>();
            Map<Long, T> map = new HashMap<>();
    
            for (T item : vos) {
        
                int level = getLevel(item.getCode());
                item.setLevel(level);
                map.put(item.getId(), item);
                if (item.getFid() == null || item.getFid() == 0 ) {
        
                    retList.add(item);
                    continue;
                }
    
                T fNode = map.get(item.getFid());
                if (null != fNode) {
        
    
                    List<Tree> subs = fNode.getChildren();
                    if (null == subs) {
        
                        subs = new ArrayList<>();
                        fNode.setChildren(subs);
                    }
    
                    subs.add(item);
                } else {
        
                    log.error("Failed to get father node: {}", item);
                }
            }
    
            return retList;
        }

## 使用循环代替向下递归 ##

#### 需求：使用循环的方式 代替菜单树的递归 ####

这个时候我们要借助第三方容器，通常使用栈或队列。

代码实现：

// 所有菜单树
                List<SysMenuDTO> allTreeList = xxx;
    
                // 一二级菜单树 level从0开始
                List<SysMenuDTO> res = new ArrayList<>();
    
                Queue<SysMenuDTO> queue = new LinkedBlockingDeque() ;
    
                for (SysMenuDTO each : allTreeList) {
        
                	// 将每个节点放入队列中
                    queue.offer(each);
                }
    
                while (!queue.isEmpty()) {
        
                	// 出队列
                    SysMenuDTO each = queue.poll();
                    if (Optional.ofNullable(each.getLevel()).orElse(0) < 2) {
        
                        res.add(each);
                    }
    
                    if (null != each.getChildren()) {
        
                        List<Tree> children = each.getChildren();
                         for (Tree eachElement : children) {
        
                         	// 子节点不为空 将子节点的每个对象入队列
                             queue.offer((SysMenuDTO) eachElement);
                         }
                    }
    
                }

[0523a099c213402085a09dafc2035d35.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a7d9aabca5f946bfa12ae55120a9676c.jpeg
[cd9ce0b540474f1fb7c3612aae423e42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f1250a5931594281ba44f0a0adae1a78.png