递归思想
定义：
递归是一种算法思想，其中一个函数直接或间接地调用自身来解决问题。递归通常包含一个基本情况（结束条件）和一个或多个递归情况（函数调用自身）。
注意点：
- 1.调用自身
- 2.设置终止条件
作用：
递归可以使复杂的问题简化为更简单的子问题，便于求解。它特别适用于具有重叠子问题和自相似结构的问题，如树、图、排序等。
递归的常规应用
我以数据结构树和栈作为演示例子
-
树的遍历：
在树结构中，递归通常用于深度优先遍历（DFS）
如前序遍历、中序遍历和后序遍历。- Demo Code：
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public void preorderTraversal(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); } -
栈的实现：
- 递归可以用于实现栈的基本操作，例如入栈和出栈。
通过递归可以实现栈的反转或深拷贝等操作。 - Demo Code：
public void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); reverseStack(stack); insertAtBottom(stack, top); } private void insertAtBottom(Stack<Integer> stack, int value) { if (stack.isEmpty()) { stack.push(value); } else { int top = stack.pop(); insertAtBottom(stack, value); stack.push(top); } } - 递归可以用于实现栈的基本操作，例如入栈和出栈。
递归在技术栈中的应用
1. 微服务的循环依赖：
- 原理：在Spring Cloud的微服务架构中，递归可以用于处理服务间的调用关系。例如，当一个服务需要调用另一个服务，而这个被调用的服务又需要回调原服务时，就可能形成递归调用。
- 示例：假设有两个服务 A 和 B，A 调用 B 的某个接口，B 在处理完请求后需要再调用 A 的另一个接口。可以使用递归来处理这种情况。
@RestController
public class ServiceAController {
@Autowired
private RestTemplate restTemplate;
@GetMapping("/callB")
public String callB() {
// 调用服务 B
return restTemplate.getForObject("http://service-b/callA", String.class);
}
}
@RestController
public class ServiceBController {
@Autowired
private RestTemplate restTemplate;
@GetMapping("/callA")
public String callA() {
// 递归调用服务 A
return restTemplate.getForObject("http://service-a/callB", String.class);
}
}
这里会有循环依赖问题，解决方案
解决循环依赖的方法
循环依赖常规解决方案一 使用异步调用：
- 将服务之间的同步调用改为异步消息传递，例如使用消息队列（如 RabbitMQ、Kafka）。这样，服务 A 可以将请求发送到消息队列，而不直接依赖于服务 B 的响应。
示例：使用消息队列解决循环依赖
假设有服务 A 和服务 B，服务 A 需要处理用户请求，并将结果发送到服务 B，而服务 B 又需要对服务 A 的结果进行反馈。
// 服务 A
@RabbitListener(queues = "requestQueue")
public void handleRequest(String request) {
// 处理请求
String result = processRequest(request);
// 发送结果到队列
rabbitTemplate.convertAndSend("responseQueue", result);
}
// 服务 B
@RabbitListener(queues = "responseQueue")
public void handleResponse(String response) {
// 处理服务 A 的结果
processResponse(response);
}
在这个例子中，服务 A 和服务 B 通过消息队列进行交互，消除了直接的循环依赖，从而避免了潜在的问题。同时，通过懒加载的方式，进一步降低了服务间的耦合度，使得服务的初始化更加灵活。
延迟加载（懒加载）：
- 利用懒加载的方式来处理循环依赖。在服务启动时，不立即初始化某些依赖，而是在需要使用时再进行初始化。可以通过 Spring 的
@Lazy注解来实现懒加载。
@Service
public class ServiceA {
private final ServiceB serviceB;
@Autowired
public ServiceA(@Lazy ServiceB serviceB) {
this.serviceB = serviceB; // 懒加载 ServiceB
}
public void someMethod() {
serviceB.performAction();
}
}
@Service
public class ServiceB {
private final ServiceA serviceA;
@Autowired
public ServiceB(@Lazy ServiceA serviceA) {
this.serviceA = serviceA; // 懒加载 ServiceA
}
public void performAction() {
serviceA.someMethod();
}
}
循环依赖常规解决方案三 配置中心：
- 在 Spring Cloud 中，可以利用配置中心（如 Spring Cloud Config）来集中管理配置和依赖，减少服务间的直接依赖。
2. 中间件RabbitMQ的应用：只是场景之一其他队列中间件同理
- 原理：在消息队列的处理中，递归可以用于实现消息的重试机制。例如，如果某个消息处理失败，可以通过递归调用来重新处理该消息，直到成功或达到最大重试次数。
- 示例：在 RabbitMQ 的消费者中，可以使用递归来实现重试机制。
@RabbitListener(queues = "myQueue")
public void consumeMessage(String message) {
try {
// 处理消息
processMessage(message);
} catch (Exception e) {
// 如果处理失败，递归重试
retryConsumeMessage(message, 1);
}
}
private void retryConsumeMessage(String message, int retryCount) {
if (retryCount <= 3) { // 最大重试次数为 3
try {
// 处理消息
processMessage(message);
} catch (Exception e) {
// 递归调用重试
retryConsumeMessage(message, retryCount + 1);
}
} else {
// 达到最大重试次数，记录日志或发送到死信队列
log.error("Message failed after retries: " + message);
}
}
3. 文件系统遍历
在操作系统中，文件系统可以被视为一个树形结构，递归地遍历文件夹和文件是常见的操作。
思路：
- 使用递归遍历每个文件夹，查找其中的文件和子文件夹。
Demo Code：
import java.io.File;
public class FileSystemTraversal {
public static void listFiles(String directoryName) {
File directory = new File(directoryName);
File[] files = directory.listFiles();
if (files != null) {
for (File file : files) {
if (file.isDirectory()) {
System.out.println("Directory: " + file.getName());
listFiles(file.getAbsolutePath()); // 递归调用
} else {
System.out.println("File: " + file.getName());
}
}
}
}
public static void main(String[] args) {
listFiles("C:\\example"); // 替换为你要遍历的目录
}
}
复杂度：
- 时间复杂度：O(n)，n 为文件数量。
- 空间复杂度：O(h)，h 为树的高度（递归栈的深度）。
4. JSON 解析
在前端开发和后端服务中，JSON 数据结构通常是嵌套的，递归解析 JSON 对象是一种常见的需求。
思路：
- 使用递归方法来遍历 JSON 对象的每个键值对，处理嵌套的情况。
Demo code：
import org.json.JSONObject;
public class JsonParser {
public static void parseJson(JSONObject jsonObject, String prefix) {
for (String key : jsonObject.keySet()) {
Object value = jsonObject.get(key);
if (value instanceof JSONObject) {
parseJson((JSONObject) value, prefix + key + "."); // 递归解析
} else {
System.out.println(prefix + key + ": " + value);
}
}
}
public static void main(String[] args) {
String jsonString = "{\"name\":\"John\", \"age\":30, \"address\":{\"city\":\"New York\", \"zip\":\"10001\"}}";
JSONObject jsonObject = new JSONObject(jsonString);
parseJson(jsonObject, ""); // 开始解析
}
}
复杂度：
- 时间复杂度：O(n)，n 为 JSON 对象中键值对的数量。
- 空间复杂度：O(h)，h 为嵌套层数。
5. 爬虫程序
在网络爬虫中，递归地访问网页并提取信息是非常常见的做法，特别是当网页内容是多层嵌套时。
思路：
- 访问网页，提取其中的链接并递归访问。
Demo Code：
import org.jsoup.Jsoup;
import org.jsoup.nodes.Document;
import org.jsoup.nodes.Element;
import java.io.IOException;
public class WebCrawler {
public static void crawl(String url, int depth) {
if (depth == 0) return; // 结束条件
try {
Document doc = Jsoup.connect(url).get();
System.out.println("Crawling: " + url);
for (Element link : doc.select("a[href]")) {
crawl(link.attr("abs:href"), depth - 1); // 递归访问链接
}
} catch (IOException e) {
System.err.println("Error crawling: " + url);
}
}
public static void main(String[] args) {
crawl("http://example.com", 2); // 从指定URL开始，限制深度
}
}
复杂度：
- 时间复杂度：O(n)，n 为访问的网页数量。
- 空间复杂度：O(h)，h 为递归栈的深度。
递归在各种技术栈中发挥着重要作用，特别是在处理树形结构、嵌套数据和复杂系统时。
理解递归的原理和应用场景对于开发者来说至关重要，可以帮助他们解决更复杂的问题。
