递归算法
前言
递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
应用场景
- 数据的定义是按递归定义的。如Fibonacci函数。
- 问题解法按递归算法实现。如Hanoi问题。
- 数据的结构形式是按递归定义的。如二叉树、广义表等。 [2]
代码示例
data数据类---模拟实体类
package maven.daily.test.mian.recursive;
public class Data {
private String id;
private String name;
private String pid;
Data(String id, String name, String pid) {
this.id = id;
this.name = name;
this.pid = pid;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getPid() {
return pid;
}
public void setPid(String pid) {
this.pid = pid;
}
}data传输类---模拟dto
package maven.daily.test.mian.recursive;
import java.util.List;
public class DataDto {
private String id;
private String name;
private String pid;
private List<DataDto> childs;
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<DataDto> getChilds() {
return childs;
}
public void setChilds(List<DataDto> childs) {
this.childs = childs;
}
public String getPid() {
return pid;
}
public void setPid(String pid) {
this.pid = pid;
}
@Override
public String toString() {
return "{id:" + id + ", name:" + name + ", pid:" + pid + ", childs:" + childs + "}";
}}
实体与传输转换类
package maven.daily.test.mian.recursive;
import java.lang.reflect.InvocationTargetException;
import org.apache.commons.beanutils.BeanUtils;
public class DataConverter {
public DataDto toDto(Data data) {
DataDto dto = new DataDto();
try {
BeanUtils.copyProperties(dto, data);
} catch (IllegalAccessException e) {
} catch (InvocationTargetException e) {
}
return dto;
}
}模拟测试类
package maven.daily.test.mian.recursive;
import java.util.ArrayList;
import java.util.List;
public class RecursiveMain {
public static void main(String[] args) {
List<Data> list = new ArrayList<>();
buildData(list);
List<DataDto> re = dealData(list);
re.forEach(t -> {
System.out.println(t);
});
}
private static void buildData(List<Data> list) {
list.add(new Data("p1", "root", null));
list.add(new Data("c111", "chid111", "c11"));
list.add(new Data("c1", "chid1", "p1"));
list.add(new Data("c12", "chid12", "c1"));
list.add(new Data("c13", "chid13", "c1"));
list.add(new Data("c112", "chid112", "c11"));
list.add(new Data("c113", "chid113", "c11"));
list.add(new Data("c2", "chid2", "p1"));
list.add(new Data("c3", "chid3", "p1"));
list.add(new Data("c4", "chid4", "p1"));
list.add(new Data("c11", "chid11", "c1"));
list.add(new Data("c21", "chid21", "c2"));
list.add(new Data("c22", "chid22", "c2"));
}
private static List<DataDto> dealData(List<Data> list) {
List<DataDto> result = new ArrayList<DataDto>();
List<Data> root = new ArrayList<Data>();
list.forEach(data -> {
if (null == data.getPid()) {
root.add(data);
}
});
DataConverter dataConverter = new DataConverter();
root.forEach(data -> {
result.add(Recursive(dataConverter.toDto(data), list));
});
return result;
}
private static DataDto Recursive(DataDto dto, List<Data> datas) {
List<DataDto> childs = new ArrayList<DataDto>();
DataConverter dataConverter = new DataConverter();
datas.forEach(t -> {
if (t.getPid() != null && t.getPid().equals(dto.getId())) {
DataDto temp = dataConverter.toDto(t);
childs.add(temp);
Recursive(temp, datas);
}
});
dto.setChilds(childs);
return dto;
}
}运行结果
{
id: p1,
name: root,
pid: null,
childs: [{
id: c1,
name: chid1,
pid: p1,
childs: [{
id: c12,
name: chid12,
pid: c1,
childs: []
}, {
id: c13,
name: chid13,
pid: c1,
childs: []
}, {
id: c11,
name: chid11,
pid: c1,
childs: [{
id: c111,
name: chid111,
pid: c11,
childs: []
}, {
id: c112,
name: chid112,
pid: c11,
childs: []
}, {
id: c113,
name: chid113,
pid: c11,
childs: []
}]
}]
}, {
id: c2,
name: chid2,
pid: p1,
childs: [{
id: c21,
name: chid21,
pid: c2,
childs: []
}, {
id: c22,
name: chid22,
pid: c2,
childs: []
}]
}, {
id: c3,
name: chid3,
pid: p1,
childs: []
}, {
id: c4,
name: chid4,
pid: p1,
childs: []
}]
}到这儿就完成了利用递归构造数型结构数据。
内容讲解
概念: 1.实体类 - 与持久层字段对应 2.数据传输类-根据业务需求构造返回满足前端展示需要的数据结构类，另外还有屏蔽特殊字段功能。 3.转换类-实现实体类向数据传输类转换的功能。
核心
递归的核心：自己调用自己；结束条件。 重点理解
image.png
递归原理
第一：每一级的函数调用都有它自己的变量。 第二：每一次函数调用都会有一次返回，并且是某一级递归返回到调用它的那一级，而不是直接返回到main()函数中的初始调用部分。 第三：递归函数中，位于递归调用前的语句和各级被调函数具有相同的执行顺序。 第四：递归函数中，位于递归调用后的语句的执行顺序和各个被调函数的顺序相反。 第五：虽然每一级递归都有自己的变量，但是函数代码不会复制。 第六：递归函数中必须包含终止递归的语句。
递归性能
一个2000左右条数据，一条sql全部查出来，利用递归构造深度为4的树形结构，还是秒出。 这个秒出是指后台运算，不计传输时间。
image.png
image.png
递归优化
- 最经典的斐波那契数列
- 尾递归
- 利用缓存
结语
本文目的只是抛砖引玉。文章多处都是蜻蜓点水。要想更好的掌握并熟练运用，还需多练，多体会，多结合其他方面的知识。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.07.10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录