【数据结构算法（一）】递归篇（常见实例讲解）

🌈键盘敲烂，年薪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，但有一些规则需要遵守：

1. 每次只能移动一个圆盘。
2. 移动过程中，大圆盘不能放在小圆盘上面。

public class Demo1 {
    static LinkedList a = new LinkedList<>();
    static LinkedList b = new LinkedList<>();
    static LinkedList 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 a, LinkedList b, LinkedList 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;
    }
}