# 递归算法

###### 应用场景

1. 数据的定义是按递归定义的。如Fibonacci函数。
2. 问题解法按递归算法实现。如Hanoi问题。
3. 数据的结构形式是按递归定义的。如二叉树、广义表等。 [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;

private String id;
private String name;
private String 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;
}

return 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 {

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);
re.forEach(t -> {
System.out.println(t);
});
}

private static void buildData(List<Data> list) {
}

private static List<DataDto> dealData(List<Data> list) {
List<Data> root = new ArrayList<Data>();
list.forEach(data -> {
if (null == data.getPid()) {
}
});
DataConverter dataConverter = new DataConverter();
root.forEach(data -> {
});
return result;
}

DataConverter dataConverter = new DataConverter();
datas.forEach(t -> {
if (t.getPid() != null && t.getPid().equals(dto.getId())) {
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: []
}]
}```

image.png

image.png

image.png

1. 最经典的斐波那契数列
2. 尾递归
3. 利用缓存

28 篇文章15 人订阅

0 条评论