蓝桥杯——巧妙地递归

一、切蛋糕思想

• 对于递归，我们可以采用思想之一，切蛋糕思想。
• 简而言之，就是将一个大问题，切成若干个小问题进行解决。
• 递归三要素：找重复、找变化、找边界
• 我们可以理解为，自己处理一小部分，剩下的部分交给别人处理（递归）
• 分解为：直接量 + 小规模子问题

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. 1~N-1从A移动到C，B为辅助

2. 把N从A移动到B

3. 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);
    }

四、结尾

• 对于蓝桥杯递归知识内容就总结这么多，若想深入学习等待后续更新。
• 我将会继续更新关于蓝桥杯方向的学习知识，感兴趣的小伙伴可以关注一下。
• 文章写得比较走心，用了很长时间，绝对不是copy过来的！
• 尊重每一位学习知识的人，同时也尊重每一位分享知识的人。
• 😎你的点赞与关注，是我努力前行的无限动力。🤩