企业官网建设流程全解析

一、递归

其实不应该给递归单独开一篇的，因为递归并不是思想，只是一种实现手段。

分治法、深度优先搜索才是思想。

如果你试图把这些思想都揉在一起，整理出一篇《递归思路》，当然越理越糊涂。

—— 所以，用递归之前，先想明白你的实现思想。

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:再根据语义倒推出递推公式

maxDepth(root)=1+Math.max(maxDepth(root.left),maxDepth(root.right))

public int maxDepth(TrNode root){ if(root==null) return 0; return 1+Math.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(node==null) return; System.out.println(node.val); preOrder(node.left); preOrder(node.righr); }

难点2 递归出口

分成两种写法，一种是第n轮退出（❤），一种是第n-1轮退出（💔）。

啥意思呢？如果我用if(root==null) return作为递归出口想在第n轮退出的话，那其实我也可以写成if(root.next==null) return，这样就属于在上一轮也就是第n-1轮做了提前判断，提前一轮退出了。哪种写法好呢？第n轮退出的写法好。

第n轮退出的话， 递归出口永远写在方法的最前面（❤）。第n-1轮退出的话，递归出口写在进入子递归之前（💔），如果有m个if分支可以进入子递归，你就要写m个递归出口。所以当然是第n轮退出的写法好。

最佳实践：以后做题一律用第n轮退出的写法，如果不行的话， 再用第n-1轮退出的写法。

关于第n轮退出，还有一种思考角度，比如二叉树，当做传来一颗空树去考虑。传来一颗空树的时候如何处理，递归出口就如何处理。比如if(root==null) return null表示“传来一颗空树的时候return null”，正好递归出口也是“当节点为null时，return null”。

误区：不要认为用if(head==null)return 就是第n轮退出，用if(head.next==null)return 就是第n-1轮退出。是否是第n轮退出的判断标准是递归出口是否写在方法的最前面。

比如反转链表这个题，递归出口写在方法的最前面，就是第n轮退出

一些实战经验，当用引用传递作为中间结果时，递归出口那里要给人家重新new一个

难点3 递归参数

形参不着急一股脑全想出来，我都是开始写递归了，缺什么补什么。甚至有的你不想传递的，可以设置成全局变量。

1、常用形参

一般有5个常用的形参。

• 题目给出的输入，比如int[] nums，也就是我们要遍历的东西
• 表示这一轮应该遍历到int[] nums哪里的指针index
• 表示哪里被遍历过的int []used数组
• 用来放结果的容器List<List<Integer>>
• 暂存中途结果的容器List<Integer>

以全排列这个题目为例：

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(n<0) return; //3、递推关系 System.out.println(nums[n]); Print(nums,n-1); }

三、递归+回溯

如果层层递归到最底层，子问题再带着自己这一层的递归结果层层递归上来就能得到问题的答案，那就是普通递归不用回溯。如果需要在半路丢掉子问题返回的递归结果，尝试另一个子问题，这种带有尝试性质、搜索性质的就是要回溯。

还有一种区别方法，当你画出递归树形图，每个结点只走一遍的就是普通递归，如果一个结点被反反复复经过，就是需要回溯。

四、递归结果（这里我也不知道我23年当时写这块想要表达什么，先放这儿吧）

思路：先求中间元素nums[mid]，然后让nums[mid]和nums[mid-1]和nums[mid+1]比较。

排除nums[mid]本身就是要求的结果以外，有两种情况：

• nums[mid]==nums[mid-1]

• nums[mid]==nums[mid+1]

此外，因为每个元素都会出现两次，只有一个元素会出现一次，那么nums一定有奇数个元素。but如果nums是11元素，那么mid的两边各5个元素，是奇数个；如果nums是9个元素，那么mid的两边各4个元素是偶数个。所以又有两种情况：

• mid的两边是奇数个元素

• mid的两边是偶数个元素

排列组合，一共四种情况！思路并不是这个题的关键

class Solution { public: int result; int singleNonDuplicate(vector<int>& nums) { //特殊情况 if(nums.size()==1) return nums[0]; deep(0,nums.size()-1,nums); return result; } void deep(int low, int high,vector<int>& nums){ //递归出口 if(low==high) { result=nums[low]; return; } int mid=(high+low)/2; //先判断num[mid]是不是只出现一次的数字 if(nums[mid]!=nums[mid-1]&&nums[mid]!=nums[mid+1]){ result = nums[mid]; return; //和右边的相同，并且右边是偶数个。那么一定在右边 }else if(nums[mid]==nums[mid+1]&&((high-low)/2)%2==0){ deep(mid+2,high,nums); //和右边的相同，并且右边是奇数个，那么一定在左边 }else if(nums[mid]==nums[mid+1]&&((high-low)/2)%2==1){ deep(low,mid-1,nums); //和左边相同，并且左边是偶数个，那么一定在左边 }else if(nums[mid]==nums[mid-1]&&((high-low)/2)%2==0){ deep(low,mid-2,nums); //和左边相同，并且左边是奇数个，那么一定在右边 }else if(nums[mid]==nums[mid-1]&&((high-low)/2)%2==1){ deep(mid+1,high,nums); } } };

我要说的关键是，这个题只需要找出“只会出现一次的数字”，不需要把递归的返回值设置成int，只需要维护一个全局变量就行了。

如果非要把递归返回值写成int类型的

23年3月21号，撕完这个题，页面还没关，就收到了京东的offer。