数据结构和算法之【递归】
目录
认识递归
递归的定义
利用递归实现几个小案例
链表的遍历
反转字符串
求N的阶乘
思路总结
多路递归
single recursion和multi recursion
斐波那契数列
递推公式
编码实现
代码优化
LeetCode-70题
题解
测试
认识递归
递归的定义
计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集
三个重点，如下
- 自己调用自己，如果每个函数对应着一种解决方案，那么自己调用自己代表着解决方案一样
- 每次调用，函数处理的数据量和上次比较会缩减，且最后会缩减至无需继续递归(即要有结束条件)
- 子集(内层函数)处理完成，外层函数才能算是调用完成
利用递归实现几个小案例
链表的遍历
package algorithm.list; import java.util.function.Consumer; /** * 这里主要介绍两种遍历方法 * 1、方式一：通过Consumer函数式接口 * 2、方式二：递归 */ public class ListForEach { public static void main(String[] args) { // 获取到链表的头节点，然后进行遍历 Node head = getHead(); // 遍历方式一 foreachOneWay(head, System.out::println); System.out.println("-------------"); // 遍历方式二 foreachTwoWay(head); } /** * 遍历方式一：通过调用方控制，传入一个函数式接口 */ public static void foreachOneWay(Node head, Consumer<Integer> consumer) { if (head == null) return; for (Node p = head; p != null; ) { consumer.accept(p.val); p = p.next; } } /** * 遍历方式二：递归 */ public static void foreachTwoWay(Node head) { if (head == null) return; recursion(head); } /** * 递归函数 */ private static void recursion(Node curr) { if (curr == null) return; System.out.println(curr.val); recursion(curr.next); // 如果在这里打印，就是倒序遍历的结果 // System.out.println(curr.val); } /** * 返回链表的头节点 */ public static Node getHead() { Node head = new Node(5); Node node1 = new Node(2); head.next = node1; Node node2 = new Node(1); node1.next = node2; Node node3 = new Node(3); node2.next = node3; Node node4 = new Node(4); node3.next = node4; return head; } private static class Node { int val; Node next; public Node() { } public Node(int val) { this.val = val; } public Node(int val, Node next) { this.val = val; this.next = next; } } }反转字符串
package algorithm.recursion; /** * 通过递归的方式反转字符串 */ public class ReserveString { public static void main(String[] args) { String oldData = "zxvcd463c3iou"; String newData = reserveString(oldData); System.out.println(newData); } /** * 实现字符串的反转 * 返回值是一个新的字符串，是参数反转后的结果 */ public static String reserveString(String data) { if (data == null || data.length() == 0) return data; StringBuilder result = recursion(new StringBuilder(), data, 0); return result.toString(); } /** * 递归函数 */ private static StringBuilder recursion(StringBuilder builder, String data, int index) { if (index >= data.length()) { return builder; } recursion(builder, data, index + 1); builder.append(data.charAt(index)); return builder; } }求N的阶乘
package algorithm.recursion; public class Factorial { public static void main(String[] args) { for (int i = 0; i < 10; i++) { System.out.println(factorial(i)); } } /** * 求非负整数的阶乘 */ public static int factorial(int n) { if (n < 0) { throw new IllegalArgumentException("非法参数"); } if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1); } }思路总结
- 确定能否使用递归进行求解
- 推导出递推关系，即父问题和子问题的关系以及递归的结束条件
多路递归
single recursion和multi recursion
- 上述使用递归实现的几个小案例中，都是每个递归函数只包含一个自身的调用，称之为单路递归(single recursion)
- 如果每个递归函数包含多个自身调用，称为多路递归(multi recursion)
斐波那契数列
递推公式
编码实现
package algorithm.recursion; /** * 斐波那契数列：每一个数字等于前两项数字之和 */ public class FibonacciSequence { public static void main(String[] args) { // 展示前12项数字 for (int i = 0; i < 13; i++) { System.out.print(fibonacciSequence(i) + "\t"); } } /** * 获取第n项数字 */ public static int fibonacciSequence(int n) { if (n < 0) { throw new IllegalArgumentException("参数异常"); } return recursion(n); } /** * 递归函数 */ private static int recursion(int n) { if (n == 0 || n == 1) { return n; } // 这里就是多路递归(multi recursion) return recursion(n - 1) + recursion(n - 2); } }代码优化
优化思路：使用缓存进行优化，记忆法空间换时间
package algorithm.recursion; import java.util.HashMap; import java.util.Map; /** * 斐波那契数列：每一个数字等于前两项数字之和 */ public class FibonacciSequence { // 缓存：key为第n项，value为第n项的值 private static final Map<Integer, Integer> cache = new HashMap<>(); public static void main(String[] args) { // 展示前12项数字 for (int i = 0; i < 13; i++) { System.out.print(fibonacciSequence(i) + "\t"); } } /** * 获取第n项数字 */ public static int fibonacciSequence(int n) { if (n < 0) { throw new IllegalArgumentException("参数异常"); } return recursion(n); } /** * 递归函数 */ private static int recursion(int n) { if (n == 0 || n == 1) { return n; } // 查缓存，如果缓存中有第n项的数字，直接返回 Integer numOfN = cache.get(n); if (numOfN != null) { return numOfN; } // 缓存中没有，就计算第n项的数字 numOfN = recursion(n - 1) + recursion(n - 2); // 将第n项的数字放入缓存中 cache.put(n, numOfN); // 这里就是多路递归(multi recursion) return numOfN; } }LeetCode-70题
题解
class Solution { // 缓存 private Map<Integer, Integer> climbStairsCache = new HashMap<>(); public int climbStairs(int n) { // 递归结束条件 if (n <= 2) return n; //查缓存 Integer nr = climbStairsCache.get(n); if (nr != null) return nr; // 多路递归 nr = climbStairs(n - 1) + climbStairs(n - 2); // 放入缓存 climbStairsCache.put(n, nr); return nr; } }