在最近的项目开发中,我遇到了两个与父子关系紧密相关的场景:评论树结构和部门树结构。具体的需求包括找出某条评论下的所有子评论id集合和找出某个部门下所有的子部门id集合。尽管在之前的项目开发经验中,我很少使用递归,但作为数据结构操作中遍历树节点的解决方案,我决定记录并分享我的递归使用经验。
首先,我会对递归的基本概念进行介绍。在Java中,递归是指在方法的定义中调用自身的过程,基于方法调用栈的原理实现。递归的关键是定义好递归的终止条件和递归调用的条件。若没有适当的终止条件或递归调用的条件不满足,递归可能会陷入无限循环,导致栈内存溢出。
递归的优点在于能够简化问题解决过程,并实现高效算法,如数据结构操作中遍历树节点。然而,递归也存在缺点,包括栈溢出风险、性能损耗和可读性不高的问题。
递归与迭代的区别
-
迭代(Iteration)
迭代通常使用for循环,能够对集合进行遍历,并在内部进行条件设置和元素值替换。
-
递归(Recursion)
递归通过方法的自调用来解决问题。下面的内容将详细介绍递归的例子。
接下来,我将以递归获取某个评论id下面所有的子级评论id为例,向读者介绍递归的过程。在此之前,我先提供一个简单的数据库评论表的demo,其中id是主键id也是评论唯一id,parent_id是该条评论的父评论id,status为1表示审核通过的状态。
那么,我们如何将21、28、29、31、32都放进一个集合里返回呢?下面的代码示例将给您一个参考。
然而,在看代码之前,我想提出一个问题:从21开始后,遍历的路线是21-28-29?还是21-28-31?还是21-29-32?或者是21-28-31-29-32?
下面是经过脱敏处理后的参看代码示例,注释都写得比较清楚了:
/**
* 这里可以看作是外部接口的调用,会得到递归的结果
* @param id
*/
private List getIdListMethod(Integer id){
ArrayList idList = new ArrayList<>();
this.getAllIdByRecursion(id, idList);
log.info("递归后得到的id集合:{}", idList);
return idList;
}
/**
* 这里是递归的过程
* @param id
* @param idList
*/
private void getAllIdByRecursion(Integer id, List idList){
LambdaQueryWrapper wrapper = new LambdaQueryWrapper<>();
//先把该id下所有的第一级子id找到
wrapper.eq(Comment::getParentId, id).eq(Comment::getStatus, NumberUtils.INTEGER_ONE);
List commentList = this.list(wrapper);
for (Comment children : commentList){
this.getAllIdByRecursion(children.getId(), idList);
}
log.info("放入集合的id为:{}", id);
idList.add(id);
}
问题的答案是:递归后得到的id集合为[21,28,31,29,32]。这是因为迭代从一棵树开始遍历到底,没有元素了再从头开始遍历,依次迭代,类似于深度优先遍历。比如,21下面有两个子id:28和29,那么会先走21-28-31这棵树,到底了后接着按照29-32遍历。
根据我的开发经验,可以通过控制递归层数和使用Stream这两种办法对递归进行改进。
控制递归层数
JVM 默认控制的递归最大深度限制在1000层,可以通过设置JVM参数来控制其深度,也可以在代码层面对递归的层数进行控制。
int depth = 0;
//递归方法调用
for (int i = 0; i < 20; i++) {
depth++;
}
if (depth > 100){
//其它操作
}
用Stream遍历
这里的核心思路是先进行数据库全量查询(10万条以内),在内存中使用Stream流操作、Lambda表达式和Java地址引用进行筛选。这种方法适用于数据总量不多的情况,如部门树。
详情请参阅 我的这篇文章
在文章小结中,我并不推荐在项目中过度使用递归,但是如果合理使用的话,递归也能成为解决特定问题的一个利器。至于怎么拿捏这个度,那就要看大家的具体情况了。Java项目中对使用递归的理解就到这里,文章如有不足和错误,或者你有更好的解决思路,欢迎大家的指正和交流!