🌈键盘敲烂，年薪30万🌈
⭐本篇讲解实例：
- 斐波那契、兔子问题、猴子吃桃问题、跳台阶问题、汉诺塔、杨辉三角
⭐用到的递归思想：
- 无记忆递归、记忆递归(重点掌握)
一、斐波那契：
问题描述：
这个数列的每个数字都是前两个数字之和，数列的第一个和第二个数规定为1
①无记忆多路递归：
- 时间复杂度：O（n^2） - 很恐怖
public class FibonaciNoMemory { // 1 1 2 3 5 8 13 21 34 55…… public static void main(String[] args) { int n = 10; //无记忆性的递归 int ans2 = noMemoryRecursion(n); System.out.println(ans2); } private static int noMemoryRecursion(int n) { if(n == 1 || n == 2){ return 1; } return noMemoryRecursion(n-1) + noMemoryRecursion(n-2); } }
②⭐记忆递归：
- 时间复杂度：O（n）
public class FibonaciRemind { public static void main(String[] args) { int n = 10; int ans = remindRecursion(n); System.out.println(ans); } private static int remindRecursion(int n) { int[] cache = new int[n+1]; Arrays.fill(cache, -1); cache[0] = 1; cache[1] = 1; return help(n-1, cache); } private static int help(int n, int[] cache) { if(cache[n] != -1){ return cache[n]; } int val = help(n-1, cache) + help(n-2, cache); cache[n] = val; return val; } }
二、兔子问题：
问题描述：
有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少?
代码同斐波那契差不多，多了个求和，这个兔子问题就是列昂纳多·斐波那契引申出的。
public class a06_rabbit { public static void main(String[] args) { int month = 10; int count = getCount(month); System.out.printf("第十个月，共%d只兔子", count); } private static int getCount(int month) { int[] cache = new int[month]; cache[0] = 1;cache[1] = 1; help(month-1, cache); int total = 1; for (int i = 0; i < month; i++) { total += cache[i]; } return total; } private static int help(int month, int[] cache) { if(cache[month] != 0){ return cache[month]; } cache[month] = help(month - 1, cache) + help(month - 2, cache); return cache[month]; } }
三、跳台阶问题：
问题描述：
鸡哥跳台阶，有时跳一阶，有时跳二阶，问，若有10层台阶，有多少种跳法
public class SkipStairs { public static void main(String[] args) { int n = 10; int ans = getCount(n); System.out.printf("共有%d种跳法", ans); } private static int getCount(int n) { return help(n); } private static int help(int n) { if(n == 1){ return 1; } if(n == 2){ return 2; } return help(n-1) + help(n-2); } }
四、汉诺塔问题：
问题描述：
有三根柱子，编号为A、B、C，开始时在柱子A上有一些个圆盘，它们按照从下到上的顺序递增（最下面的最大，最上面的最小）。现在要将这些圆盘从柱子A移动到柱子C，中间可以借助柱子B，但有一些规则需要遵守：
- 每次只能移动一个圆盘。
- 移动过程中，大圆盘不能放在小圆盘上面。
public class Demo1 { static LinkedList<Integer> a = new LinkedList<>(); static LinkedList<Integer> b = new LinkedList<>(); static LinkedList<Integer> c = new LinkedList<>(); public static void main(String[] args) { a.addLast(3); a.addLast(2); a.addLast(1); move(3, a, b, c); } private static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) { if(n == 0){ return; } //转移n-1个到b - 要借助c move(n-1, a, c, b); //将最大的移到C c.add(a.removeLast()); myPrint(); //将n-1个到c - 要借助a move(n-1, b, a, c); } private static void myPrint() { System.out.println(a); System.out.println(b); System.out.println(c); System.out.println("==============="); } }
五：杨辉三角问题：
问题描述：有个三角形，每一行的该数等于上一行同列数+上一行前一列的数
①无记忆递归：
public class Demo2 { public static void main(String[] args) { int n = 6; print(n); } private static void printSpace(int n){ for (int i = 0; i < n; i++) { System.out.print(" "); } } private static void print(int n) { for (int i = 0; i < n; i++) { printSpace((n-i-1)*2); for (int j = 0; j <= i; j++) { System.out.printf("%-4d", getElement(i, j)); } System.out.println(); } } private static int getElement(int row, int col){ if(col == 0 || col == row){ return 1; } return getElement(row-1, col-1) + getElement(row-1, col); } }
②⭐记忆递归：
public class Demo1 { public static void main(String[] args) { int n = 6; print(n); } private static void printSpace(int n){ for (int i = 0; i < n; i++) { System.out.print(" "); } } private static void print(int n) { int[][] cache = new int[n][]; for (int i = 0; i < n; i++) { printSpace((n-i-1)*2); cache[i] = new int[i+1]; for (int j = 0; j <= i; j++) { System.out.printf("%-4d", getElement(cache, i, j)); } System.out.println(); } } private static int getElement(int[][] cache, int row, int col){ if(cache[row][col] > 0){ return cache[row][col]; } if(col == 0 || col == row){ cache[row][col] = 1; return 1; } cache[row][col] = getElement(cache, row-1, col-1) + getElement(cache, row-1, col); return cache[row][col]; } }
六、猴子吃桃问题：
问题描述：
有一只猴子摘了一堆桃子，第一天它吃了其中的一半，并再多吃了一个；第二天它又吃了剩下的桃子的一半，并再多吃了一个；以后每天都吃了前一天剩下的一半并再多吃了一个。到第n天想再吃时，发现只剩下一个桃子。问这堆桃子原来有多少个？
public class MonkeyEatPeach { public static void main(String[] args) { int days = 9; // 假设猴子在第9天时发现只剩下一个桃子 // 调用计算桃子数量的方法 int result = calculatePeaches(days); // 输出结果 System.out.println("猴子摘的桃子总数为：" + result); } // 计算桃子数量的方法 public static int calculatePeaches(int days) { if(days == 1){ return 1; } return (calculatePeaches(days - 1) + 1) * 2; } }
