数据结构和算法之【递归】

目录认识递归递归的定义利用递归实现几个小案例链表的遍历反转字符串求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, ConsumerInteger 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 MapInteger, 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 MapInteger, 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; } }测试结果