一、切蛋糕思想
- 对于递归，我们可以采用思想之一，切蛋糕思想。
- 简而言之，就是将一个大问题，切成若干个小问题进行解决。
- 递归三要素：找重复、找变化、找边界
- 我们可以理解为，自己处理一小部分，剩下的部分交给别人处理（递归）
- 分解为：直接量 + 小规模子问题
1.1 经典求阶乘
- 求阶乘
- jc(n)：求n的阶乘 jc(n-1)：求n-1的阶乘
- 1.找重复： n*(n-1) ————子问题
- 2.找变化：变化的量应该作为参数
- 3.找边界：出口
public class 递归 {
public static int jc(int n) {
if(n == 1)
return 1;
return n * jc(n-1);
}
}
1.2 打印i到j
- 1.找重复：理解为我处理当前参数问题，剩下的部分交给这个函数处理（规模更小的子问题）
- 2.找变化：变化的量应该作为参数
- 3.找边界：出口
public static void print(int i, int j) {
// 出口
if(i > j) return;
System.out.println(i);
// 重复与变化
print(i+1,j);
}
1.3 数组求和
- 当我们发现无法进行递归时，肯定是我们的参数不够
public static int sum(int[] arr,int start) {
if(start == arr.length)
return 0;
return arr[start] + sum(arr,start+1);
}
1.4 翻转字符串
- 使用递归对一个字符串进行翻转
public static String reverse(String str, int end) {
if(end == 0)
return ""+str.charAt(0);
return str.charAt(end) + reverse(str,end-1);
}
二、递归公式与等价转换思想
- 和上面切蛋糕思想不同的是，这种问题我们无法进行切分，但是我们都可以转换成数学问题，当找到数学问题后进行等价转换即可。
- 分解为：多个子规模小问题
2.1 经典斐波那契数列
- F(n) = F(n-1) + F(n-2)
// 求斐波那契数列第n项的值
public static int fib(int n) {
// 3. 找出口
if(n == 1 || n == 2) return 1;
// 1.找变化 | 2.找重复
return fib(n-1) + fib(n-2);
}
2.2 最大公约数
- 经典的欧几里得算法也称之为辗转相除法
- 通过最大公约数我们也可以判断两个数是否互质
- F(m,n) = F(n,m%n)
public static int zzxc(int m, int n) {
if(n == 0) return m;
return zzxc(n,m%n);
}
2.3 递归形式的插入排序
- 同样是利用切分思想，我们对数组前k-1个元素进行排序
- 最后处理最后一个单独的元素
- 递归都是父问题转换成子问题
public static void insertArr(int[] arr, int k) {
// 1.对数组前k-1个元素进行排序
insertArr(arr, k - 1);
// 2.将最后一个元素插入到排好序的数组中
int temp = arr[k]; // 记录该数
while(temp < arr[k-1]) { // 后一个数比前一个数小的情况，将大的数后移
arr[k] = arr[k-1]; // 直到找到适合自己的位置为止
k--;
}
arr[k] = temp;
}
三、搞不清楚的汉诺塔
- 1~N从A移动到B，C作为辅助
等价于：
-
1~N-1从A移动到C，B为辅助
-
把N从A移动到B
-
1~N-1从C移动到B，A为辅助
/**
* 八、汉诺塔问题
* 将N个盘子从source移动到target的路径打印
* @param N 初始的N个从小到大的盘子，N是最大编号
* @param from 原始柱子
* @param help 辅助的柱子
* @param to 目标柱子
*/
public static void printHanoiTower(int N, String from, String to, String help) {
printHanoiTower(N-1, from, help, to);
System.out.println("move" + N + "from" + from + "to" + to);
printHanoiTower(N-1, help, to, from);
}