递归

递归有两条特征:

  • 执行时范围不断缩小,这样才能触底反弹。
  • 终止判断在调用递归的前面。

首先可以几张图了解一下递归

image-20231220205022635

编程中两个很经典的题目: 菲波那耶数列和阶乘

//阶乘
    public static int factorial(int num) {
        if (num == 0 || num == 1) {
            return 1;
        }
        return num * factorial(num - 1);
    }
//菲波那耶数列
 public static int feibo(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (n == 0) {
            return 0;
        }
        return feibo(n - 1) + feibo(n - 2);
    }

当n没有限制n==0的时候,需要对2进行限制,否则返回时没有f(0)

上面的代码简化优化:

 public static int feibo(int n) {
        if (n<=2) {
            return 1;
        }
      
        return feibo(n - 1) + feibo(n - 2);
    }

最后是一个流程图:

image-20231220212000705

递归进阶

首先看图

image-20240304102820832

master公式:

规模相同:例如: **T(n)=a*T(n/b)+ 0(n^c) **公式中

例如归并排序中,我们不从1/2进行分开,而变成两个2/3进行划分,这样虽然会降低效率,但是子问题规模相同

a,b,c解释:

a:调用次数

b:子问题规模1/2,或是2/3

c:调用行为之外的时间复杂度

master公式结论:

可以记:log(b,a)与c更大的一个决定时间复杂度

  1. 如果log(b,a)<c,复杂度为:0(n^c)
  2. 如果log(b,a)>c,复杂度为:0(n^log(b,a))
  3. 如果log(b,a)==c,复杂度为:0(n^c*logn)

补充:**T(n)=2T(n/2)+ 0(nlogn),*时间复杂度是0(n((logn)的平方))

证明比较复杂,可以直接记结论;