目录
前言
大家好呀！我是大雄！一个菜鸡！接下来的几个月和大家分享一下自己在备战蓝桥中遇到的一些问题。感谢大家提出好的思路以及好的学习方法。我提前在这里谢谢大家了，也希望大家能够在蓝桥中取得好的名次。我们一起共勉！加油！！！
本周主要练习的题目是递归，因为每天也就给练习算法的时间大约是一个多小时，所以整体进度比较缓慢，只希望自己能够赎回报名费，当然也要像其他算法大佬学习！欢迎各位算法大佬对大雄提出的意见和建议，我一定会认真听取的。接下来我们进入正题，递归。
递归，当学习完成基础语法后，进入算法界可能是我们遇到的第一个问题。当我们看着简单的递归代码却想不清楚代码具体逻辑的时候，推荐大家去看一部电影——盗梦空间。最开始我在学习完递归之后一头雾水，当时老师就推荐去看这部电影。看完整部电影之后好像还是似懂非懂。
递归
递归：及“函数的自己调用自己”,这个可能就是我们的第一印象吧。
官方的回答是：递归是指一种或多种简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
递归解决的问题
在现实生活中，有很多问题比较复杂，直接解决这个问题比较困难，但是这些问题可以被分解为n个较小规模与原结构相似的子问题，通过解决这些相对简单的子问题，得到子问题的解，然后将子问题的解合并，从而得到原问题的解。(上边的文字多读几遍)
上边虽然说的简单对子问题的拆分，如何拆分？
递归的三要素
- 终止条件：当递归函数符合这个规则是，不在进行自己调用自己。从而避免死递归。
- 继续推进：每一次递归，都要将子问题进行划分，朝着终止条件进行，否则无法结束递归。
- 设计法则: 也就是根据递归的规律，写出递归代码。
递归设计的经验:
1）找重复（子问题划分）
2）找重复中的变化量——>参数
3）找参数变化趋势——>递归出口
递归的练习（由浅入深）
1.循环改为递归
eg:计算1-100之内累加和？
这应该是学完for循环的练习题目，接下来我们先按照for循环的形式，然后更具三要素逐步转化为递归的形式。
//for循环
int count=0;
for (int i = 1; i <=100 ; i++) {
count+=i;
}
System.out.println(count);//递归
static int fun3(int n) {
if (n == 1)
return 1;
return n+fun3(n-1);
}分析:
- 找重复：n+(n-1),求n-1的累加就是原问题的重复(规模更小)——子问题
- 找变化：每次都是n+(n-1)
- 设置出口：每次都是n-1,会朝着1这个方向下去，直到等于1然后递归结束。
我是这样理解的：fun3是张三，最近张三落难了，手头只有10万，急需100万。于是靠着自己“法外狂徒”的名号，向小弟借钱。张三小弟自己把自己的钱拿出来然后在想自己的小弟借钱，然后把自己的钱和借自己小弟的钱给张三。直到凑够100万张三就不凑了！
2.斐波那契
斐波那契数列是一串递增的整数，其中每一项都是前两项的和。这个数列从0和1开始，其前几项为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …。以此类推，第n项的值可以表示为F(n)。
斐波那契数列的性质：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) 对于所有 n > 1
递推的做法:
static void fun4(int n) {
// 求斐波那契的第n项
// 0 1(第一项) 1 2 3 5
int f1 = 1, f2 = 1, fn = -1;
if (n == 1) {
System.out.println(f1);
} else if (n == 2) {
System.out.println(f2);
} else {
for (int i = 3; i <= n; i++) {
// 后一项=前一项+前第二项
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
System.out.println(fn);
}
}递归的做法：
// 斐波那契数列
static int Fibonacci(int n){
if(n==1||n==2){
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
}分析(递归):
- 找重复：求n项需要求n-1项和n-1项，并将n-1项和n-2项加起来，如果实在想不明白可以把n当前3,然后将n-1就是2和n-2就是1,在进行调用自生就是1+1等于2。递归结束。
- 找变化：n-1项+n-1项
- 设置出口：斐波那契的第一项和第二项都等于1
3.汉诺塔问题
汉诺塔问题是一个古老而著名的数学问题，源于印度的一个古老传说。这个问题涉及三个柱子，通常标记为A、B和C。这三个柱子上分别堆叠着若干数量的圆盘，圆盘的大小不同，且按照从小到大的顺序从下到上堆叠在A柱子上。
汉诺塔问题的目标是在遵循一定规则的前提下，将所有的圆盘从一个柱子移动到另一个柱子。具体规则如下：
- 每次只能移动一个圆盘。
- 在移动过程中，任何时候都不能将一个较大的圆盘放在一个较小的圆盘上面。
- 可以利用第三个柱子（B柱子）作为辅助柱子，即可以在B柱子上暂时放置圆盘。
- 对于任何一个具体的步骤，实际上都需要进行三次移动：
- 将上面的n-1个盘子从起始柱子（如A）移到另一个柱子（如B）；
- 将最大的盘子从起始柱子移到目标柱子（如C）；
- 最后，将n-1个盘子从临时柱子（如B）移到目标柱子（如C）
个人分析：
- 开始所有的盘子都在A柱子，从上到下(从小到大)及1—n-1看做一个整体，最后一个最大的盘子看做一个整体，现将1—n-1移动到C柱，B柱作为辅助的柱子。
- 将A柱最大的盘子移动到B柱
- 将C柱的盘子移动到B柱，借助A柱作为辅助的柱子。
static void hanoiTower(int N,String from,String to,String help){
//N为盘子的个数，按照从小到大排序
// from 原始柱子 to 到达的柱子 help 辅助的柱子
if(N==1){
// 移动最后一个盘子
System.out.println("move"+N+"from"+from+"to"+to);
return;
}
//把前n-1个盘子移动到辅助空间
hanoiTower(N-1,from,help,to);
// N移动到target
System.out.println("move"+N+"from"+from+"to"+to);
// 让前n-1个盘子所在的辅助空间移动到源空间
hanoiTower(N-1,help,to,from);
}总结
本篇主要介绍的是递归的基本概念以及基本的题目，有些比较难得题目我现在也没有头绪好像之后还需要学习分治思想，学习完之后应该可以学会把，自我感觉递归这里有些题目还不太透彻，希望大佬们能给出学习的建议和学习困难题目的方法。
