一、递归其实不应该给递归单独开一篇的因为递归并不是思想只是一种实现手段。分治法、深度优先搜索才是思想。如果你试图把这些思想都揉在一起整理出一篇《递归思路》当然越理越糊涂。—— 所以用递归之前先想明白你的实现思想。1、整体感觉错误的理解方式写递归不能总想着去把递归平铺展开这样脑子里就会循环一层一层往下调然后再一层一层返回试图想搞清楚计算机每一步都是怎么执行的这样就很容易被绕进去。对于递归代码这种试图想清楚整个递和归过程的做法实际上是进入了一个思维误区。正确的理解方式不要一层层深入下去看而是把后面的部分理解成“已经递归完的结果”。 比如说二叉树的题就把问题看成根节点左子树递归完的结果和右子树递归完的结果。不要再深入左子树、右子树了。具体点讲如果一个问题 A 可以分解为若干子问题 B、C、D你可以假设子问题 B、C、D 已经解决在此基础上思考如何解决问题 A。而且你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可不需要一层一层往下思考子问题与子子问题子子问题与子子子问题之间的关系。也就是说递归只能考虑当前层和下一层的关系不能继续往下深入。我们需要屏蔽掉递归细节理解为完成了某种功能的语义描述即可。这样就很好找到递推公式我们就能很轻松地写出递归代码。如果深入看的话是这样的根本无穷无尽CPU烧了也捋不明白再就是递归是什么样子的呢以八皇后为例for循环8次的话递归图是这样画的有几个循环就有几个结点。二叉树就是上图那个样子也可以看成for循环两次。2、递归模板 / 如何写递归一句话最佳实践先弄清楚你的实现思想是计算二叉树深度那样的分治法还是电话号码组合那样的深度优先搜索。然后递归一定要先画图。画图的过程中就能写出递推关系以及递归出口递归出口记得用第n轮退出的写法然后一边写一边补充必要的递归参数不想传递的甚至可以写成全局变量。dfs(//1.参数都要传递什么这也是个难点){ //2.递归出口 if(){ return; } //3.递推关系。多的话用for循环少的话比如二叉树直接并列写就行了 for(){ //递推关系 dfs(); } }关于上面的for循环还要再以八皇后为例for循环8次的话递归图是这样画的有几个循环就有几个结点。结点少的话比如二叉树直接并列写就行了难点1 递推关系递归的思路其实跟动态规划的递推是一样的三步走step01:先定义递归问题的语义注意参数也是定义中的一部分step02:再用语义表达出和子问题之间的递归关系step03:再根据语义倒推出递推公式例1比如最大二叉树的最大深度这个题就可以把递归方法maxDepth(root)定义成以root为节点树的最大深度这句话就是maxDepth(root)的语义。再根据语语义再反推出递归公式比如语义上是一棵树的最大深度等于左子树深度和右子树深度的最大值1那我们就可以推出递归公式maxDepth(root)1Math.max(maxDepth(root.left),maxDepth(root.right))进而写出代码public int maxDepth(TrNode root){ if(rootnull) return 0; return 1Math.max(maxDepth(root.left),maxDepth(root.right)); }例2二叉树的先序遍历step01定义递归问题F(Root)为:先序遍历以Root为根节点的二叉树 step02语义先序遍历以Root为根节点的二叉树相当于先遍历根节点root再先序遍历左子树再先序遍历右子树 step03语义倒推出递推公式F(Root)遍历Root节点F(Root.left)F(Root.right)进而根据递推公式写出代码public void preOrder(TreeNode node){ if(nodenull) return; System.out.println(node.val); preOrder(node.left); preOrder(node.righr); }难点2 递归出口分成两种写法一种是第n轮退出❤一种是第n-1轮退出。啥意思呢如果我用if(rootnull) return作为递归出口想在第n轮退出的话那其实我也可以写成if(root.nextnull) return这样就属于在上一轮也就是第n-1轮做了提前判断提前一轮退出了。哪种写法好呢第n轮退出的写法好。第n轮退出的话 递归出口永远写在方法的最前面❤。第n-1轮退出的话递归出口写在进入子递归之前如果有m个if分支可以进入子递归你就要写m个递归出口。所以当然是第n轮退出的写法好。最佳实践以后做题一律用第n轮退出的写法如果不行的话 再用第n-1轮退出的写法。关于第n轮退出还有一种思考角度比如二叉树当做传来一颗空树去考虑。传来一颗空树的时候如何处理递归出口就如何处理。比如if(rootnull) return null表示“传来一颗空树的时候return null”正好递归出口也是“当节点为null时return null”。误区不要认为用if(headnull)return 就是第n轮退出用if(head.nextnull)return 就是第n-1轮退出。是否是第n轮退出的判断标准是递归出口是否写在方法的最前面。比如反转链表这个题递归出口写在方法的最前面就是第n轮退出一些实战经验当用引用传递作为中间结果时递归出口那里要给人家重新new一个难点3 递归参数形参不着急一股脑全想出来我都是开始写递归了缺什么补什么。甚至有的你不想传递的可以设置成全局变量。1、常用形参一般有5个常用的形参。题目给出的输入比如int[] nums也就是我们要遍历的东西表示这一轮应该遍历到int[] nums哪里的指针index表示哪里被遍历过的int []used数组用来放结果的容器ListListInteger暂存中途结果的容器ListInteger以全排列这个题目为例2、回溯-值传递的巧妙写法学会了值传递回溯的巧妙写法直接把加法运算、字符串拼接运算写到子方案参数里这样就不用写成下面这样的“穿脱原则”了。但是仅限于值传递哈引用传递的话只能老老实实的穿脱原则。二、一个最简单的递归来看这个题给你学会递归的信心问题逆序打印一个数组递推公式假设令F(n)逆序遍历长度为n的数组 那么F(n) 打印数组中下标为n的元素 F(n-1)终止条件if (n 0) return ;递归代码//1.参数传递全局nums得传n得传 public void Print(int[] nums,int n){ //2.递归出口。一律用第n轮退出的写法 if(n0) return; //3、递推关系 System.out.println(nums[n]); Print(nums,n-1); }三、递归回溯如果层层递归到最底层子问题再带着自己这一层的递归结果层层递归上来就能得到问题的答案那就是普通递归不用回溯。如果需要在半路丢掉子问题返回的递归结果尝试另一个子问题这种带有尝试性质、搜索性质的就是要回溯。还有一种区别方法当你画出递归树形图每个结点只走一遍的就是普通递归如果一个结点被反反复复经过就是需要回溯。四、递归结果这里我也不知道我23年当时写这块想要表达什么先放这儿吧思路先求中间元素nums[mid]然后让nums[mid]和nums[mid-1]和nums[mid1]比较。排除nums[mid]本身就是要求的结果以外有两种情况nums[mid]nums[mid-1]nums[mid]nums[mid1]此外因为每个元素都会出现两次只有一个元素会出现一次那么nums一定有奇数个元素。but如果nums是11元素那么mid的两边各5个元素是奇数个如果nums是9个元素那么mid的两边各4个元素是偶数个。所以又有两种情况mid的两边是奇数个元素mid的两边是偶数个元素排列组合一共四种情况思路并不是这个题的关键class Solution { public: int result; int singleNonDuplicate(vectorint nums) { //特殊情况 if(nums.size()1) return nums[0]; deep(0,nums.size()-1,nums); return result; } void deep(int low, int high,vectorint nums){ //递归出口 if(lowhigh) { resultnums[low]; return; } int mid(highlow)/2; //先判断num[mid]是不是只出现一次的数字 if(nums[mid]!nums[mid-1]nums[mid]!nums[mid1]){ result nums[mid]; return; //和右边的相同并且右边是偶数个。那么一定在右边 }else if(nums[mid]nums[mid1]((high-low)/2)%20){ deep(mid2,high,nums); //和右边的相同并且右边是奇数个那么一定在左边 }else if(nums[mid]nums[mid1]((high-low)/2)%21){ deep(low,mid-1,nums); //和左边相同并且左边是偶数个那么一定在左边 }else if(nums[mid]nums[mid-1]((high-low)/2)%20){ deep(low,mid-2,nums); //和左边相同并且左边是奇数个那么一定在右边 }else if(nums[mid]nums[mid-1]((high-low)/2)%21){ deep(mid1,high,nums); } } };我要说的关键是这个题只需要找出“只会出现一次的数字”不需要把递归的返回值设置成int只需要维护一个全局变量就行了。如果非要把递归返回值写成int类型的23年3月21号撕完这个题页面还没关就收到了京东的offer。