一文搞明白java遍历循环、递归、深度优先、广度优先的区别
表设置
| 列名 | 类型 |
|---|---|
| id | varchar |
| parentId | varchar |
| 其他字段 |
... |
使用循环与使用递归的区别是什么？
-
递归即是自己调用自己，凡是方法内的有调自己的都属于递归。
public void exampleMethod() {exampleMethod() ;}
-
循环不存在自己调用自己，循环可以嵌套。
public void exampleMethod() {for(int i = 0 ; i < length ; i ++) {for(int j =0 ; j < size; j ++) {}}}
-
函数调用是有时间和空间消耗的，每一次函数调用，都需要再内存中分配空间以保存参数、返回地址及临时变量。而且往栈里压入数据和弹出数据都需要时间，更何况，每个进程的栈的容量是有限的。因此，递归实现的效率不如循环。 -
抛开业务、场景等因素，循环和递归是可以相互改写的。 但是一般情况下用递归要比循环的代码逻辑上好理解一些。
深度优先和广度优先
-
什么是深度优先？打个不恰当的比喻，吃面时，你总是一根根的吃，一根不吃完，你不会吃其他的。 -
什么是广度优先？还是吃面，你总一大口一大口的吃，但是一口吃到嘴巴，你咽不下去，只能咬断了，先咽了再吃另外一口。 -
编码实例
用递归实现深度优先
public List<ImageText> getListByParentId(String parentId) {return this.imageTextDao.getListByParentId(parentId);}//递归private void count(List<Long> statistics , List<ImageText> imageTextArray) {for(ImageText imageText : imageTextArray) {statistics.add(1L) ;List<ImageText> tempChilds2 = this.imageTextService.getListByParentId(imageText.getId()) ;if (CollectionUtils.isNotEmpty(tempChilds2)) {this.count(statistics, tempChilds2);}}}//方法入口public Long countRelayById(String id) {List<Long> statistics = Lists.newArrayList() ;List<ImageText> imageTextArray = this.imageTextService.getListByParentId(id) ;this.count(statistics, imageTextArray) ;return statistics.size() ;}
用循环实现广度优先
public List<ImageText> getListByParentId(String parentId) {return this.imageTextDao.getListByParentId(parentId);}//循环public Long countRelayById(String id) {Long statistics = 0l ;List<ImageText> imageTextArray = this.imageTextService.getListByParentId(id) ;while(CollectionUtils.isNotEmpty(imageTextArray)) {List<ImageText> tempChilds = null ;for (ImageText child : imageTextArray) { // 遍历子节点// ------------// 获取child内容，或其他处理// ------------statistics ++ ;List<ImageText> tempChilds2 = this.imageTextService.getListByParentId(child.getId()) ;if (CollectionUtils.isNotEmpty(tempChilds2)) {if(tempChilds == null) {tempChilds = Lists.newArrayList() ;}tempChilds.addAll(tempChilds2);}}imageTextArray = tempChilds;}return statistics;}