蓝桥杯——巧妙地递归

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

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过来的!
  • 尊重每一位学习知识的人,同时也尊重每一位分享知识的人。
  • ????你的点赞与关注,是我努力前行的无限动力。????