递归指的是方法或函数自身调用自身,适用于一个功能被重复使用,而每一次使用时的参数是由上次的结果来确定的情况。本文介绍了递归在实际工作场景中的应用。

以下是将一个多层结构数据转换成树形结构的实例,该实例能够很好的展示递归的使用方式。

数据

  • 原始数据
id parentId value
1 0 one
2 1 two
3 1 three
4 2 four
5 2 five
6 3 six
7 4 seven
8 4 eight
9 4 nine
10 5 ten
11 6 eleven
12 9 twelve
  • 层级结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
{
"id": 1,
"value": "one",
"nodes": [
{
"id": 2,
"value": "two",
"nodes": [
{
"id": 4,
"value": "four",
"nodes": [
{
"id": 7,
"value": "seven",
"nodes": []
},
{
"id": 8,
"value": "eight",
"nodes": []
},
{
"id": 9,
"value": "nine",
"nodes": [
{
"id": 12,
"value": "twelve",
"nodes": []
}
]
}
]
},
{
"id": 5,
"value": "five",
"nodes": [
{
"id": 10,
"value": "ten",
"nodes": []
}
]
}
]
},
{
"id": 3,
"value": "three",
"nodes": [
{
"id": 6,
"value": "six",
"nodes": [
{
"id": 11,
"value": "eleven",
"nodes": []
}
]
}
]
}
]
}

Java递归的实现

递归得到树形结构

  • Model类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Item {
private Integer id;
private Integer parentId;
private String value;
private List<Item> nodes;

public Integer getId() {
return id;
}

public void setId(Integer id) {
this.id = id;
}

public Integer getParentId() {
return parentId;
}

public void setParentId(Integer parentId) {
this.parentId = parentId;
}

public String getValue() {
return value;
}

public void setValue(String value) {
this.value = value;
}

public List<Item> getNodes() {
return nodes;
}

public void setNodes(List<Item> nodes) {
this.nodes = nodes;
}
}
  • Mapper类
1
2
3
4
5
6
7
8
9
10
11
@Mapper
public interface ItemMapper {
@Select("select * from table where parentId = #{parentId:INTEGER}")
List<Item> getSubItemsByParentId(Integer parentId);

@Select("select id from table where parentId = #{parentId:INTEGER}")
List<Integer> getSubItemIds(Integer parentId);

@Select("select * from table where id = #{id:INTEGER}")
Item getItemById(Integer id);
}
  • Service类
1
2
3
4
5
6
7
public interface ItemService {
Item getItemTree();

List<Integer> getSubItemIds(Integer itemId);

List<Integer> getParentItemIds(Integer itemId);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Service("itemService")
public class ItemServiceImpl implements ItemService {
@Autowired
private ItemMapper itemMapper;

@Override
public Item getItemTree() {
Item rootItem = itemMapper.getItemById(1);
setItemTree(1, rootItem);
return rootItem;
}

private void setItemTree(Integer itemId, Item item) {
List<Item> subItems = itemMapper.getSubItemsByParentId(itemId);
if (subItems != null && subItems.size() > 0) {
for(Item subItem : subItems) {
setItemTree(subItem.getId(), subItem);
}
item.setNodes(subItems);
}
}
}

递归获取指定item所有父item ID的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Service("itemService")
public class ItemServiceImpl implements ItemService {
@Autowired
private ItemMapper itemMapper;

@Override
public List<Integer> getParentItemIds(Integer itemId) {
return getParentItemIds(itemId, new ArrayList<>());
}

private List<Integer> getParentItemIds(Integer itemId, ArrayList<Integer> resultIds) {
Item item = itemMapper.getItemById(itemId);
if (item != null && item.getParentId() > 0) {
resultIds.add(item.getParentId());
getParentItemIds(item.getParentId(), resultIds);
}
return resultIds;
}
}

递归获取指定item下所有子item ID的集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Service("itemService")
public class ItemServiceImpl implements ItemService {
@Autowired
private ItemMapper itemMapper;

@Override
public List<Integer> getSubItemIds(Integer itemId) {
return getSubItemIds(itemId, new ArrayList<>());
}

private List<Integer> getSubItemIds(Integer itemId, ArrayList<Integer> resultIds) {
List<Integer> subItemIds = itemMapper.getSubItemIds(itemId);
if (subItemIds != null && subItemIds.size() > 0) {
resultIds.addAll(subItemIds);
for (Integer subItemId : subItemIds) {
getSubItemIds(subItemId, resultIds);
}
}
return resultIds;
}
}