最近疯狂备战蓝桥杯，做了一些笔记，也许会有一些错误，欢迎与大家交流分享，在这与大家分享，互相学习交流！
微信：panpan668706
知乎：大牛带我飞吧
微信公众号：大牛带我飞吧
视频来源：蓝桥杯官方-视频-循环与递归
递归与循环
- 理论上，任何循环都可以重写为递归的形式
- 有时候，为栈限制，需要尾递归
- java不支持尾递归
- 有些语言没有循环语句 只能使用递归
- 改为递归的关键是发现逻辑“相似性”
- 不能忘记递归的出口
例：从0打印到n
可以使用循环的语句
我负责打印最后一个n
但是我前面的人负责打印0–n-1
字符串得比较当中也会 使用到 递归得调用
首先：
- 如果没有明显的相似性 需要主构造
- 不能相似的原因很可能是确实参数
- 递归与数学上的地推公式很类似
递归：
- 递归调用仅仅是被调用函数恰巧是主函数本身
- 注意每次调用的层数不同
- 注意每次分配形参并非同一个变量
- 注意返回的次序
递归和go to是不一样的！
现场的记录 通过一个栈结构 要转还没有转的时候 讲现场保存！接着往下执行B,栈结构就是后人先出。
n:相当于现场信息 每一层都会保存现场信息 一层一层的压栈 到n=0时 这时我在栈顶，我下面保存着多个不同值得n
就是说是逐层得深入 逐层得返回回来！
总结：任何得循环总能够改成递归 两个重点：相似性 出口
第二讲：经典问题
在n个球当中，任意取出m个（不放回），求有多少种不同得取法？
public class A{
//解题方式：我就想象有一个特殊球x,划分得方法 包涵特殊球x嘛 思维实验 造出内部得结构
public static int f(int n,int m){
//操场上分成两类 一定取幸运球 一定不取幸运球
//出口问题：
if(n<m) return 0;//如果是只有两个球 让我取三个 不可能
if(n==m) return 1;//只有一种取值方式
if(m==0) return 1;//取出0个 只有一种方式
return f(n-1,m-1)+(n-1,m)
}
public static viod main(String[] args)
{
int k=f(10,3);
System.out.println(k);
}
}
球n个元素得全排列
public class B{
//把第一个元素放在这 到底是哪一个元素呢 轮流放到这个位置 其他元素进行全排列
//传入得参数必须是变化得
public static void f(char[] data，int k//当前得交换位置,与其后得元素得交换){
//让n个元素一次放到第一位
第一层：第0个元素 与后面得每个元素进行交换
第一层：第1个元素 与后面得每个元素进行交换
第一层：第2个元素 与后面得每个元素进行交换
第一层：第i个元素 与后面得每个元素进行交换
//递归得出口 for循环得循环终止得时候 就是递归得出口
if(k==data.length-1){
//当我得k 已经是最后一个关注点了 就可以打印了
for(){
//通过for循环就能够讲 排序得数组进行打印出来了
}
}
for(int i =k;i<data.length;i++){
char t=k=data[k];//考查得是第k个元素
data[k]=data[i];
data[i]=data[t];
//做了交换以后 就可以进行递归
f(data,k+1);
//我们注意：交换以后 要进行回溯 不能影响起始条件 分析一下！！迷宫问题，八皇后问题 试探以后进行回溯
}
}
public static void main(String[] args){
char[] data="ABCDE".toCharArray();
f(data);
}
}
备注：n个开关 +电灯 试探 回溯
求两个串得最大公共子序列得长度
abcdef abc abd bdf //最大子序列要比字串多
考虑：问题是否可解 问题是否可以进行有优化
如果是很长得串，递归得时间是很长得，就会出现可行性得问题。
设法使得规模降低，缩短这个串，折半，采用得是去掉头元素，剩下的字串就可以进行出来，我也可以考虑最后一个元素。递归参数一定要有变化，不行得话，可以增加参数。将复杂的问题变小话。