递归算法使用
1.什么是递归算法
通常递归算法可以将一个问题的重复调用进行分解，将其分解成一个多次调用，最终完成筛选或者需要的数据。比如我们常见的斐波那契数列就是这样的：
0、1、1、2、3、5、8、13、21、34这样的递归数据，可以通过此来总结出它的数学公式规律：
F(0) = 0;
F(1) = 1;
F(n) = F(n-1) + F(n-2);(n >= 2)
将其转成程序可以写成：
public static int getFn(int n){
//先排除不满足的条件，然后针对特定场景的条件，最后是共性的实现
if(n < 0){
return -1;
}
if(n == 0){
F(0) = 0;
}
if(n==1){
F(1) = 1;
}
if(n >1){
F(n) = F(n-1) + F(n-2);
}
}
而F(n) = F(n-1) + F(n-2)的这个过程就是是借助上面的F(0)和F(1)的结果来进行递推的，这个过程在数学上是一个数列的递推公式，在高中我们学过的数列上。我还记得当时求解递推公式可以使用函数方程，而函数方程的思想想想其实是借助了微分方程逆推得到积分方程的过程,或者说是采用不动点法可以实现这一求解的过程。这个过程，在我看到高等数学的时候才明白，现在想来确实很想笑，^_^….
而这个过程是重复的，因此我们可以提取出共性的部分，借助共性的部分进行重复，即可得到我们想要的结果。
2.项目中使用递归
而在我们的项目中，经常会出现像树形菜单的需求。比如我们想将权限做成按钮级别，这个时候就需要做一个树形菜单，可以让用户根据需要进行启用和禁用。而树形菜单由于有父子级别，因此我们如果需要将菜单返回给前端，通常是需要将其组装成树形结构的。下面用自己去年做的一个需求来说明吧，需求是做一个医疗文书的需求，涉及到文件的上传，同时将文件的PDF、PPT、word转成图片,这里省略掉了文件上传和文件转换操作，只涉及树形递归操作。菜单树的效果是可以实现打印，同时可以进行新增子项，可以进行启用和禁用操作。此时的启用和禁用涉及到父子关系的操作。
树形菜单目录
此时涉及到一个流的操作和用户可以根据需要可以自己去订阅自己的字典目录，进行文件的传输。也即文件流操作和树形结构以及pdf、ppt、word和图片的转换。
在此之前，我们可以将字典的名称放在一个顶尖目录为0的目录上，然后将字典的名称展示出来，也即是一级目录，此时的目录以层次进行划分，而一级目录是在字典目录中新增的。这样我们就可以进行我们的递归操作了。
如果需要进行递归，此时我们首先需要进行设计事先在文件目录中涉及一个顶尖目录，它是以0开头的。然后后面的都是可以依次为基础的。
树的数据结构：当时写的时候借鉴了网上的资料进行了自己的数据组装
public class MenuTree {
private List<HdMedicalDocPO> menuList;
public MenuTree(List<HdMedicalDocPO> menuList) {
this.menuList = menuList;
}
// 建立树形结构
public List<HdMedicalDocPO> builTree() {
List<HdMedicalDocPO> treeMenus = new ArrayList<>();
for (HdMedicalDocPO menuNode : getRootNode()) {
menuNode = buildChilTree(menuNode);
treeMenus.add(menuNode);
}
return treeMenus;
}
// 递归，建立子树形结构
private HdMedicalDocPO buildChilTree(HdMedicalDocPO pNode) {
List<HdMedicalDocPO> chilMenus = new ArrayList<>();
for (HdMedicalDocPO menuNode : menuList) {
if (menuNode.getPDocCode().equals(pNode.getDocCode())) {
chilMenus.add(buildChilTree(menuNode));
}
}
pNode.setChildren(chilMenus);
return pNode;
}
// 获取根节点
private List<HdMedicalDocPO> getRootNode() {
List<HdMedicalDocPO> rootMenuLists = new ArrayList<>();
for (HdMedicalDocPO menuNode : menuList) {
if (menuNode.getPDocCode().equals("0")) {
rootMenuLists.add(menuNode);
}
}
return rootMenuLists;
}
}
进行业务处理：
/**
* @description 获取患者医疗文书树形结构
* @author lyz
* @date 2020/6/24 19:21
* @param isEnable
**/
@RequestMapping("getTreeData")
@ApiOperation(httpMethod = "POST", value = "获取患者医疗文书树形结构")
public HttpResult<List<HdMedicalDocPO>> getTreeData(@ApiParam(name = "isEnable") @RequestParam(required = false) Boolean isEnable) {
HttpResult<List<HdMedicalDocPO>> result = new HttpResult<>();
Integer fkTenantId = UserUtils.getTenantId();
List<HdMedicalDocPO> list = hdMedicalDocService.listByEnableFkId(isEnable, fkTenantId);
List<HdMedicalDocPO> medicalDocPOList;
// 说明此时会进行禁用操作筛选，拿到与之相关的禁用父子菜单，然后进行树的构建
if (Objects.nonNull(isEnable) && Objects.equals(isEnable, false)) {
// 找出所有的节点信息至顶级
medicalDocPOList = builSelectTree(list);
// 构建菜单树
MenuTree menuTree = new MenuTree(medicalDocPOList);
list = menuTree.builTree();
} else {
MenuTree menuTree = new MenuTree(list);
list = menuTree.builTree();
}
result.setRs(list);
return result;
}
进行菜单式的构建：
/**
* @description 进行禁用条件筛选, 这里先筛选处理所有与禁用相关的父子操作，然后进行构建
* @author lyz
* @date 2020/6/24 10:12
* @param menuList
**/
public List<HdMedicalDocPO> builSelectTree(List<HdMedicalDocPO> menuList) {
// 拿到所在租户所有的菜单
List<HdMedicalDoc> listAll = hdMedicalDocService.listByFkTenantId(UserUtils.getTenantId());
List<HdMedicalDocPO> hdMedicalDocPOList = new ArrayList<>();
for (HdMedicalDocPO menuNode : menuList) {
// 进行递归操作，将数据放入到数据中
recursiveTree(hdMedicalDocPOList, menuNode, listAll);
hdMedicalDocPOList.add(menuNode);
}
hdMedicalDocPOList = hdMedicalDocPOList.stream().collect(Collectors
.collectingAndThen(Collectors.toCollection(() -> new TreeSet<>(Comparator.comparing(HdMedicalDocPO::getDocCode))), ArrayList::new));
return hdMedicalDocPOList;
}
基于菜单树进行树的递归操作：
/**
* @description 递归菜单树
* @author lyz
* @date 2020/6/24 10:10
* @param hdMedicalDocPOList
* @param menuNode
* @return void
**/
private void recursiveTree(List<HdMedicalDocPO> hdMedicalDocPOList, HdMedicalDocPO menuNode, List<HdMedicalDoc> listAll) {
if (!Objects.equals(menuNode.getPDocCode(), "0")) {
hdMedicalDocPOList.add(menuNode);
HdMedicalDoc medicalDoc = null;
// 进行匹配
for (HdMedicalDoc hdMedicalDoc : listAll) {
if (hdMedicalDoc.getDocCode().equals(menuNode.getPDocCode())) {
medicalDoc = hdMedicalDoc;
}
}
// 将父菜单设置为当前菜单，并进行进一步拿到顶级菜单
HdMedicalDocPO medicalDocPO = BeanUtils.copyProperties(medicalDoc, HdMedicalDocPO.class);
recursiveTree(hdMedicalDocPOList, medicalDocPO, listAll);
} else {
// 到了顶级，终止一次递归操作
hdMedicalDocPOList.add(menuNode);
}
}
这是自己当时写好的业务和递归，文件上传和文件转换、打印就不在这里展示了，以上就是分享给大家的。
3.遇到的问题和解决
想写好递归，首先想好需要写的关系，这样递归就可以很好的写出来了。在这过程中，我也遇到过，当时文件上传的时候，我在本地测试上传的时候，没有什么问题。但是当时测试安装的软件是wps的，而我安装的是office的软件。他测试的时候，给我提了一个bug。在他的系统没有出现问题，当时我用了一个jacob的jar包，因此当时也是因为使用这个包的原因，所以在测试的过程中和测试配合发现，当时的jacob包在我调用PDF转图片的时候，会使用jacob调用offcie中的active中的函数，因此会出现wps出现问题的情况。同时在这个过程中，也发现一些坑，就是当时使用的poi在3.13版本的时候，不支持图片、pdf的正常转换。当时将poi升级成了3.14之后，发现支持。当时还因为升级poi怕影响excel的导入导出操作，还做了一些测试和检查。同时也说明了一个问题，就是如果软件升级的时候，还是最好使用一些比较新和稳定的版本，这样一些已知的bug被修复，一些功能可以正常使用。
4.总结
什么时候该使用递归，遇到的问题是重复性操作，同时有终止的条件，可以进行递推，此时就可以考虑。同时这个问题可以进行分解。递归的使用还是很广泛的，比如机器学习中，经常基于一个公式进行递推。比如常用的菜单树，都是可以使用递归的。
腾讯云开发者
