前言
遞歸算法（英語(yǔ)：recursion algorithm）在計(jì)算機(jī)科學(xué)中是指一種通過(guò)重復(fù)將問(wèn)題分解為同類(lèi)的子問(wèn)題而解決問(wèn)題的方法。遞歸式方法可以被用于解決很多的計(jì)算機(jī)科學(xué)問(wèn)題明未，因此它是計(jì)算機(jī)科學(xué)中十分重要的一個(gè)概念舔株。絕大多數(shù)編程語(yǔ)言支持函數(shù)的自調(diào)用泉哈，在這些語(yǔ)言中函數(shù)可以通過(guò)調(diào)用自身來(lái)進(jìn)行遞歸旨指。計(jì)算理論可以證明遞歸的作用可以完全取代循環(huán)宏侍，因此在很多函數(shù)編程語(yǔ)言（如Scheme）中習(xí)慣用遞歸來(lái)實(shí)現(xiàn)循環(huán)桥帆。
應(yīng)用場(chǎng)景
- 數(shù)據(jù)的定義是按遞歸定義的医增。如Fibonacci函數(shù)慎皱。
- 問(wèn)題解法按遞歸算法實(shí)現(xiàn)。如Hanoi問(wèn)題叶骨。
- 數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的茫多。如二叉樹(shù)、廣義表等忽刽。 [2]
代碼示例
data數(shù)據(jù)類(lèi)---模擬實(shí)體類(lèi)
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傳輸類(lèi)---模擬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 + "}";
}
}
實(shí)體與傳輸轉(zhuǎn)換類(lèi)
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;
}
}
模擬測(cè)試類(lèi)
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;
}
}
運(yùn)行結(jié)果
{
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: []
}]
}
到這兒就完成了利用遞歸構(gòu)造數(shù)型結(jié)構(gòu)數(shù)據(jù)天揖。
內(nèi)容講解
概念:
1.實(shí)體類(lèi) - 與持久層字段對(duì)應(yīng)
2.數(shù)據(jù)傳輸類(lèi)-根據(jù)業(yè)務(wù)需求構(gòu)造返回滿足前端展示需要的數(shù)據(jù)結(jié)構(gòu)類(lèi)，另外還有屏蔽特殊字段功能跪帝。
3.轉(zhuǎn)換類(lèi)-實(shí)現(xiàn)實(shí)體類(lèi)向數(shù)據(jù)傳輸類(lèi)轉(zhuǎn)換的功能今膊。
核心
遞歸的核心：自己調(diào)用自己；結(jié)束條件伞剑。
重點(diǎn)理解
image.png
遞歸原理
第一：每一級(jí)的函數(shù)調(diào)用都有它自己的變量斑唬。
第二：每一次函數(shù)調(diào)用都會(huì)有一次返回，并且是某一級(jí)遞歸返回到調(diào)用它的那一級(jí)纸泄，而不是直接返回到main()函數(shù)中的初始調(diào)用部分赖钞。
第三：遞歸函數(shù)中，位于遞歸調(diào)用前的語(yǔ)句和各級(jí)被調(diào)函數(shù)具有相同的執(zhí)行順序聘裁。
第四：遞歸函數(shù)中雪营，位于遞歸調(diào)用后的語(yǔ)句的執(zhí)行順序和各個(gè)被調(diào)函數(shù)的順序相反。
第五：雖然每一級(jí)遞歸都有自己的變量衡便，但是函數(shù)代碼不會(huì)復(fù)制献起。
第六：遞歸函數(shù)中必須包含終止遞歸的語(yǔ)句。
遞歸性能
一個(gè)2000左右條數(shù)據(jù)镣陕，一條sql全部查出來(lái)谴餐，利用遞歸構(gòu)造深度為4的樹(shù)形結(jié)構(gòu)，還是秒出呆抑。
這個(gè)秒出是指后臺(tái)運(yùn)算岂嗓，不計(jì)傳輸時(shí)間。
image.png
image.png
遞歸優(yōu)化
- 最經(jīng)典的斐波那契數(shù)列
- 尾遞歸
- 利用緩存
結(jié)語(yǔ)
本文目的只是拋磚引玉鹊碍。文章多處都是蜻蜓點(diǎn)水厌殉。要想更好的掌握并熟練運(yùn)用，還需多練侈咕，多體會(huì)公罕，多結(jié)合其他方面的知識(shí)。
