文章目录

  • 一、初识递归
  • 二、缓存
  • 三、分治
  • 四、回溯

一、初识递归

递归函数 = 终止条件 + 递归关系
终止条件: 当大问题被拆解成能轻松解决的小问题时,运行终止条件中的逻辑
递归关系: 定义如何将大问题拆解为小问题

例子:小名跑步。
例如:小名跑4公里,可以分为(跑1km+再跑3km)-> (跑1km+再跑2km)-> (跑1km+再跑1km)-> (跑完全程)
实现:

public void running(int distance) {    if (distance == 0) { // 终止条件        System.out.println("小名跑完了全程!");        return;    } else {        System.out.println("小名跑了1km");        distance = distance - 1;        System.out.println("还剩" + distance + "km");        running(distance); // 递归调用    }}@Testpublic void test1() {    int distance = 4;    System.out.println("跑步总程:" + distance + "km");    running(distance);}

输出:

跑步总程:4km小名跑了1km还剩3km小名跑了1km还剩2km小名跑了1km还剩1km小名跑了1km还剩0km小名跑完了全程!

正如:LeetCode: 700. 二叉搜索树中的搜索
树对象:

public class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode() {    }    TreeNode(int val) {        this.val = val;    }    TreeNode(int val, TreeNode left, TreeNode right) {        this.val = val;        this.left = left;        this.right = right;    }    @Override    public String toString() {        return "TreeNode{" +                "val=" + val +                ", left=" + left +                ", right=" + right +                '}';    }}

主要方法:

public TreeNode searchBST(TreeNode root, int val) {    // 终止条件    if (root == null) return null; // 搜索完所有节点,目标节点不存在    if (root.val == val) return root; // 当前节点即为目标节点    // 递归(已知:二叉搜索树(BST)右子树节点值大于左子树节点值)    if (val > root.val) return searchBST(root.right, val); // 目标值大于当前节点,开始搜索右子树    else return searchBST(root.left, val); // 目标值大于当前节点,开始搜索左子树}

测试:

@Testpublic void test() {    TreeNode treeNode1 = new TreeNode(1);    TreeNode treeNode3 = new TreeNode(3);    TreeNode treeNode7 = new TreeNode(7);    TreeNode treeNode2 = new TreeNode(2,treeNode1,treeNode3);    TreeNode treeNode4 = new TreeNode(4,treeNode2,treeNode7);    TreeNode treeNode = searchBST(treeNode4, 2);    System.out.println(treeNode == null ? null : treeNode.toString());}

输出:

TreeNode{val=2, left=TreeNode{val=1, left=null, right=null}, right=TreeNode{val=3, left=null, right=null}}

递归三种形式:
1.Memorization缓存:将计算结果保存,避免重复计算
2.Divide and conquer分治:将一个大问题分解成小问题,各个击破,然后将“小问题的解”组合起来
3.Backracking回溯:逐步尝试所有满足条件的结果,一旦发现不可行的解,立即停止。

二、缓存

  1. 初始化缓存
  2. 如果缓存中存在答案,则直接返回
  3. 将计算结果写入缓存

正如:LeetCode:509. 斐波那契数

题目提示中提到:
f(0) = 0,f(1) = 1
f(n) = f(n – 1) + f(n – 2),其中 n > 1
所以我不难计算出f(2)=1,从上图我们可以看出f(2)被计算了两次,所以这里我们用缓存来减少加法的次数。

public int fib(int n) {    //1.初始化缓存    int[] memo = new int[n+1];    int res = helper(memo, n);    return res;}public int helper(int[] memo, int n){    if (n < 2) {        return n;    }    //2.如果缓存中存在答案,则直接返回    if(memo[n]!=0){        return memo[n];    }    //3.将计算结果写入缓存    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);    return memo[n];}

测试:

@Testpublic void test3(){    int fib = fib(4);    System.out.println(fib);}

输出:

3

三、分治

  1. 把大问题分为一系列小问题
  2. 递归求解每个子问题
  3. 合并每个子问题的结果
    二叉搜索树(BST):左子树的所有值要比根节点小;右子树的所有值要比根节点大

正如:LeetCode:98. 验证二叉搜索树

public boolean isValidBST(TreeNode root) {    return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean helper(TreeNode node, long lower, long upper){    if (node == null) {        return true;    }    if (node.val <= lower || node.val >= upper) {        return false;    }    return helper(node.left,lower,node.val) && helper(node.right,node.val,upper);}

helper方法解读:
当入参是左子树节点,要限制所有其他节点比该节点小(限制上界是节点val)
当入参是右子树节点,要限制所有其他节点比根节点大(限制下界是节点val)
省略树对象:见上一小节

测试:

@Testpublic void test5(){    System.out.println("--------------示例1--------------");    TreeNode treeNode11 = new TreeNode(1);    TreeNode treeNode33 = new TreeNode(3);    TreeNode treeNode22 = new TreeNode(2,treeNode11,treeNode33);    System.out.println(isValidBST(treeNode22));    System.out.println("---------------示例2-------------");    TreeNode treeNode1 = new TreeNode(1);    TreeNode treeNode3 = new TreeNode(3);    TreeNode treeNode6 = new TreeNode(6);    TreeNode treeNode4 = new TreeNode(4, treeNode3, treeNode6);    TreeNode treeNode5 = new TreeNode(5, treeNode1, treeNode4);    System.out.println(isValidBST(treeNode5));}

示例1(来自LeetCode):

示例2(来自LeetCode):

输出:

--------------示例1--------------true---------------示例2-------------false

四、回溯

  1. 迭代所有可能的候选对象
  2. 试试这个部分候选解决方案
  3. 给定候选者,进一步探索
  4. 回溯

正如:LeetCode:22. 括号生成

图片来源

从上文的例子中,可以看出递归的题目都可以被画成树状图。本题要求是“有效的”括号组合,所以肯定不可能由右括号开始。之后就是尝试列举所有括号组合情况了,当括号数量达到 2n 这就是我们的终止递归的条件了。这里值得注意的是:左括号的数量不能大于n,而且右括号的数量不能大于左括号的数量,显然这样是不符合题目“有效的”括号组合规定的

public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {    // 终止条件    if (cur.length() == 2 * max) {        ans.add(cur.toString());        return;    }    // 左括号不能超过最大值    if (open < max) {        // 试探添加左括号        backtrackV2(ans, cur.append("("), open + 1, close, max);        // 回溯        cur.deleteCharAt(cur.length() - 1);    }    // 右括号数量不能大于左括号数量    if (close < open) {        // 试探添加右括号        backtrackV2(ans, cur.append(")"), open, close + 1, max);        // 回溯        cur.deleteCharAt(cur.length() - 1);    }}public List<String> generateParenthesis(int n) {    List<String> ans = new ArrayList<String>();    backtrack(ans, new StringBuilder(), 0, 0, n);    return ans;}

测试

@Testpublic void test6(){    List<String> strings = generateParenthesis(3);    System.out.println(strings);}

输出:

[((())), (()()), (())(), ()(()), ()()()]

小名心得:在使用回溯法式,我们只需考虑清楚:方法外部的入参出参,方法内部的限制条件终止条件即可,无需过于关系代码是如何帮你实现的。也无需添加打印语句查看程序的执行顺序,那样只会越看越懵,所以我们只需考虑好,我们要怎样得到想要的结果即可。

参考内容:
【小小福讲算法】硅谷工程师十五分钟带你深入理解 Recursion (递归)算法,及其衍生出的算法(分治算法Divide and Conquer, 回溯 Backtracking)

参考内容中的大佬把递归讲的很好理解,感兴趣的小伙伴可以去看下(B站搬运版)。本文是小名学习后的总结,若有错误理解,希望大家可以在评论区纠正小名。感谢大家