目录
一、递归
1.1递归的概念
1.1.1定义
定义：递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集。
比如单链表递归遍历的例子：
void f(Node node) { if(node == null) { return; } println("before:" + node.value) f(node.next); println("after:" + node.value) }
说明：
- 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）。
- 每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归。
- 内层函数调用（子集处理）完成，外层函数才能算调用完成。
1.1.2原理
假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的伪码
// 1 -> 2 -> 3 -> null f(1) void f(Node node = 1) { println("before:" + node.value) // 1 void f(Node node = 2) { println("before:" + node.value) // 2 void f(Node node = 3) { println("before:" + node.value) // 3 void f(Node node = null) { if(node == null) { return; } } println("after:" + node.value) // 3 } println("after:" + node.value) // 2 } println("after:" + node.value) // 1 }
1.1.3思路
- 确定能否使用递归求解
- 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件
- 深入到最里层叫做递
- 从最里层出来叫做归
- 在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到
1.2单路递归
1.2.1阶乘
用递归方法求阶乘
- 阶乘的定义 $n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n$，其中 n 为自然数，当然 0! = 1
编辑
代码实现：
private static int fac(int num) { if (num < 1) { return 1; } return num * f(num - 1); }
拆解伪码如下，假设 n 初始值为 3:
f(int num = 3) { // 解决不了,递 return 3 * f(int num = 2) { // 解决不了,继续递 return 2 * f(int num = 1) { if (num < 1) { // 可以解决, 开始归 return 1; } } } }
1.2.2正向输出数字
public static void Print(int num){ if(num>9){ Print(num/10); } System.out.print(num%10); }
1.2.3反向输出字符串
用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置。
- 递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
- 归：从 n == str.length() 开始归，从归打印，自然是逆序的
编辑
public static void Print(String str,int index){ if(index<str.length()-1){ Print(str,index+1); } //System.out.println(str.substring(index,index+1)); System.out.println(str.charAt(index)); }
拆解伪码如下，假设字符串为 "abc"。
void reversePrint(String str, int index = 0) { void reversePrint(String str, int index = 1) { void reversePrint(String str, int index = 2) { void reversePrint(String str, int index = 3) { if (index == str.length()) { return; // 开始归 } } System.out.println(str.charAt(index)); // 打印 c } System.out.println(str.charAt(index)); // 打印 b } System.out.println(str.charAt(index)); // 打印 a }
1.3多路递归
1.3.1斐波那契数列
概念：如果每个递归函数例包含多个自身调用，称之为 multi recursion
编辑
public static int fib(int num) { if (num == 0) { return 0; } if (num == 1) { return 1; } return fib(num - 1) + fib(num - 2); }
编辑
1.3.2兔子问题
编辑
- 第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）
- 第二个月，它们成熟
- 第三个月，它们能产下一对新的小兔子（蓝色）
- 所有兔子遵循相同规律，求第 n 个月的兔子数
分析
兔子问题如何与斐波那契联系起来呢？设第 n 个月兔子数为 f(n)
- f(n) = 上个月兔子数 + 新生的小兔子数
- 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
- 因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
- 上个月兔子数，即 f(n-1)
- 上上个月的兔子数，即 f(n-2)
f(n)=f(n-1)+f(n-2);
因此本质还是斐波那契数列，只是从其第一项开始
1.3.3青蛙爬楼梯
- 楼梯有 n 阶
- 青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
- 只能向上跳，问有多少种跳法
编辑
- 因此本质上还是斐波那契数列，只是从其第二项开始
- 对应 leetcode 题目 70. 爬楼梯 - 力扣（LeetCode）
1.4汉诺塔问题
该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
编辑
设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：
(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；
(2)将A杆中剩下的第n号盘移至C杆；
(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。
递归法：
实际操作中，只有第二步可直接完成，而第一、三步又成为移动的新问题。以上操作的实质是把移动n个盘子的问题转化为移动n-1个盘，那一、三步如何解决？事实上，上述方法设盘子数为n, n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3… … 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。
//代码实现： public static void Tower(int num,char A,char B,char C){ //num表示盘子的个数，A,B,C表示A塔，B塔，C塔 if(num==1){ System.out.println("移动:"+A+"到"+C); } else{ //如果有多个盘子，可以看成两个，最下面的，上面所有的盘子(num-1) //(1.)先移动上面所有的盘子到B盘，借助C盘 Tower(num-1,A,C,B); //(2.)把最下面的盘移动到C盘 System.out.println("移动:"+A+"到"+C); //(3.)再把B塔上的盘子移动到C盘，借助A盘 Tower(num-1,B,A,C); } }
1.5猴子吃桃问题
猴子吃桃子问题: 有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个! 以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时， 想再吃时(即还没吃)，发现只有1个桃子了。问题:最初共多少个桃子?
//代码实现 //猴子吃桃问题 //day10：1个桃子 //day9:(day10+1)*2 //day8:(day9+1)*2 public static int Peach(int day){ if(day<0||day>10){ return -1; } if(day==10){ return 1; } else if(day>=1&&day<=9){ return (Peach(day+1)+1)*2; } return -1; }
1.6老鼠走迷宫问题
目标：小球从1-1走到6-5
编辑
迷宫问题：
1.小球得到的路径，和程序员设置的找路策略有关：找路的上下左右的先后顺序
//代码实现 public static void main(String[] args) { //思路： //1.设置迷宫，通过二维数组表示int[][] map=new int[8][7]; //2.规定：0表示可以走，1表示障碍物 int[][] map=new int[8][7];//8行7列 for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[i].length; j++) { //设置最上面一行和最下面一行为1 map[0][j]=1; map[7][j]=1; if(i>=1&&i<7){ //设置最右面和最左面一列为1 map[i][0]=1; map[i][6]=1; } } } //输出迷宫 disPlay(map); //设置障碍物 map[2][1]=1; map[2][2]=1; disPlay(map); //找路 findWay(map,1,1); disPlay(map); } public static void disPlay(int[][] map){ System.out.println("=============================="); for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[i].length; j++) { System.out.print(map[i][j]+" "); } System.out.println(); } } public static boolean findWay(int[][] map,int i,int j){ //1.findWay方法找出迷宫的路径 //2.如果找到，返回true，否则返回false //3.i,j表示老鼠的位置，初始化的位置为(1,1); //4.0表示可以走，1表示障碍物，2表示可以走，3表示走过但是走不通，是一条死路 //5.当map[5][6]==2，说明找到了通路，此时就可以结束，否则继续找 if(map[6][5]==2){//说明已经找到 return true; } else{ if(map[i][j]==0){ //表示当前位置可以走 //假定该位置可以走通 map[i][j]=2; //找路的逻辑：我的：右下左上（逻辑不通找路结果不同）或者【下右上左】 if(findWay(map,i,j+1)){//右 return true; } else if(findWay(map,i+1,j)){//下 return true; } else if(findWay(map,i,j-1)){//左 return true; } else if(findWay(map,i-1,j)){//上 return true; } else{ map[i][j]=3; return false; } } else{ return false; } } }
2.存在回溯现象
//修改上述部分代码 //设置障碍物 map[3][1]=1; map[3][2]=1; map[2][2]=1; disPlay(map);
二、递归的时间复杂度
递归式： 
其中
- T(n) 是问题的运行时间，n 是数据规模
- a 是子问题个数
- T(\frac{n}{b}) 是子问题运行时间，每个子问题被拆成原问题数据规模的 \frac{n}{b}
- f(n) 是除递归外执行的计算
