一说起循环,大家都会说一个例子:“从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山...” 这是一个死循环,假如加上一个终止条件,第五个和尚就结束故事了,那就是一个循环了。
下一个讲故事的和尚 与 当前讲故事的和尚是没有联系,并也不会对下一个和尚产生影响, 只是在固定代码受循环次数影响。
递归呢!下一个讲故事的和尚 与 当前讲故事的和尚是联系,会对下一个和尚产生影响, 在固定代码受传入方法参数影响。
递归是一层一层进入,再原路返回,虽然每一层都一样,但是下一层受到上一层传入参数的影响,原路返回的结果告诉上一层,上一层处理再告诉上一层。
跟《盗梦空间》类似,它是一层层的,并且还能处理再次处理上一层。
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 分治是需要利用到递归进行优化滴。
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;
}