算法：递归和分治-理论
引入递归
一说起循环，大家都会说一个例子：“从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山...” 这是一个死循环，假如加上一个终止条件，第五个和尚就结束故事了，那就是一个循环了。
下一个讲故事的和尚 与 当前讲故事的和尚是没有联系，并也不会对下一个和尚产生影响， 只是在固定代码受循环次数影响。
什么是递归
递归呢！下一个讲故事的和尚 与 当前讲故事的和尚是联系，会对下一个和尚产生影响， 在固定代码受传入方法参数影响。
递归是一层一层进入，再原路返回，虽然每一层都一样，但是下一层受到上一层传入参数的影响，原路返回的结果告诉上一层，上一层处理再告诉上一层。
跟《盗梦空间》类似，它是一层层的，并且还能处理再次处理上一层。
一个例子：计算 n!。
public int pow(int n) {
if (n <= 1) return 1;
int last = pow(n - 1); //得到下一层的结果
return n * last; //当前层和下一层结果进行处理
}我们一层层的看n！的处理
递归，从获取参数6，调用自身传递参数5->4->3->2->1，当参数为1 ，结束递归，开始返回倒数的2层， 当前层可以与上一层进行业务处理，并再次返回上一层。
为了更方便的使用和记住递归，一群人琢磨了这样的一个套路。
public int pow(int n) { //int n 控制递归层级
if (n <= 1) return 1; //递归终止条件 （递归出口）
int last = pow(n - 1); //深入下一层
int result = n * last; //当前层级的业务处理（业务流程逻辑）
return result; //如果需要，反转当前级别状态
}什么是分治
假如我们现在处理的这个问题，特别复杂、浪费资源等等问题，反正就是完美实现很困难，我们怎么办，一般做法都是分层，把困难的问题分成几个简单问题，然后再进行解决。
例如，计算机网络，把一个网络传输分而治之 ， OSI模型7 应用层 6 表示层 5 会话层 4 传输层 3 网络层 2 数据链路层 1 物理层。
一个例子：小写字母转化为大写字母
通过把字符串进行拆分，把大问题拆分成小问题，分而治之， 充分利用现代计算机多核系统，同时处理小问题，再进行合并操作。
说了好像等于没说，看起来好像有点意思，但是实际用不到的感觉。
NO、NO、NO 分治是需要利用到递归进行优化滴。
另一个例子：leetcode:144二叉树的前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list; //递归出口
list.add(root.val);
//把问题划分成两个，求左右节点是否满足。
list.addAll(preorderTraversal(root.left));
list.addAll(preorderTraversal(root.right));
return list;
}同样额为了更方便的使用和记住分治，一群人琢磨了这样的一个套路。
public List<Integer> preorderTraversal(TreeNode root) { //node控制递归层级
ArrayList<Integer> list = new ArrayList<>();
if (root == null) return list; //递归终止条件（递归出口）
list.add(root.val);
TreeNode left = root.left //数据准备
TreeNode right= root.right
list.addAll(preorderTraversal(left)); //对子问题进行递归处理，并对子结果数据合并
list.addAll(preorderTraversal(right));
return list;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-08-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录