一.如何理解递归
递归对于初学者来说是一个非常抽象的概念,笔者在第一次学习时也是迷迷糊糊的(二叉树遍历),递归的代码看起来非常的简洁,优美,但是如何想出来递归的思路或者为什么能用递归这是初学者很难分析出来的
笔者在学习的过程中通过刷题,也总结出自己的一些经验,总结来说就是要胆大心细,宏观看待问题
其实很多递归的问题如果从宏观的角度去看,其实特别简单,比如二叉树的后序遍历,他无非就是:
- 你先给我一个根节点
- 访问根节点的左子树
- 访问根节点的右子树
- 再打印当前节点的值
对于每一个节点的操作都是相同的,如果从宏观的角度看,我们可以把一个复杂的二叉树想象成一个只有三个节点的二叉树
把二叉树的后序遍历就当做访问这个只有三个节点的二叉树,按照左右根的顺序遍历
dfs(TreeNode root) { if(root == null) return; dfs(root.left);// 访问左节点 dfs(root.right);// 访问右结点 println(root.val);// 打印当前节点的值 }
大致总结下来递归问题的思路如下:
分析:根据题目分析,判断是否有重复的子问题,如果有,就可以利用递归解决,设计出函数头,从宏观的角度想,要完成这次操作,这个"接口"需要什么参数(二叉树的遍历需要root,快排需要一个数组和开始结束位置)设计函数体:只关注某一个子问题的具体操作,比如二叉树的后序遍历的子问题就完成三步:访问左子树,访问右子树,打印当前节点递归出口:确定好递归出口,将子问题分割到最小单元进行确定,比如二叉树的遍历当节点为空时就不需要再去执行任何操作了,直接返回即可,快排,分割到数组只有一个数字或者为空时(l >= r)就不需要继续分治了
二.例题解析:
1.汉诺塔问题
链接:https://leetcode.cn/problems/hanota-lcci/description/
分析:
函数头:给我三个柱子和盘子数函数体:先借助c将a上的n-1个盘子移动到b,然后将a剩余的最大的盘子移动到c,再借助a,将b上的n-1个盘子移动到c递归出口:当只有一个盘子的时候,直接移动
代码:
class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { int n = A.size(); dfs(A,B,C,n); } private void dfs(List<Integer> a, List<Integer> b, List<Integer> c,int n) { // 递归结束条件 只有一个盘子的时候直接移动 if(n == 1) { c.add(a.remove(a.size() - 1)); return; } // 模拟:借助c,将a上的n-1个盘子移动到b上 dfs(a,c,b,n-1); // 将最大的盘子移动到c上 c.add(a.remove(a.size() - 1)); // 模拟:借助a,将b盘上的n-1个盘子移动到c上 dfs(b,a,c,n-1); } }
2.合并两个有序链表
链接: https://leetcode.cn/problems/merge-two-sorted-lists/
分析:
函数头:两个链表的头结点函数体:判断较小值,合并之后的所有节点,并连接返回的节点递归出口:只有一个节点或者为空
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 递归 if(list1 == null) return list2; if(list2 == null) return list1; // 将后面的链表给我合并好,并且返回合并好的节点 if(list1.val < list2.val) { list1.next = mergeTwoLists(list1.next,list2); return list1; }else { list2.next = mergeTwoLists(list2.next,list1); return list2; } } }
算法系列--递归(一)--与链表有关（下）https://developer.aliyun.com/article/1480789?spm=a2c6h.13148508.setting.33.361f4f0eyTL4lb
