递归专题

递归函数的时间复杂度计算

Master公式

N 表示问题的规模
a 表示递归的次数，也就是生成的子问题数
N/b 表示子问题的规模，子问题规模一致时才能使用Master公式。
O(N^d) 表示除了递归操作之外，其余操作的时间复杂度
T 表示该递归函数的时间复杂度

public static int getMax(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int mid = (L + R) / 2;
        int maxLeft = getMax(arr, L, mid);
        int maxRight = getMax(arr, mid + 1, R);
        return Math.max(maxLeft, maxRight);
    }

通过Master公式得到如下：

递归三要素

1. 递归函数
2. 递归边界
3. 递推公式

   递归函数

   明确函数的具体功能是干什么的，入参是什么，返回值是什么。后者的确定都是俄为了给上层调用或者全局的一个数据，这也是递归函数的三个基本要素。

   递归边界

   考虑函数入参的边界值，最开始不一定要完善，可以在后续一步步完善边界值。边界值的作用，一是可以作为异常值的边界，二是作为递归结束的判断边界。

   递推公式

   地推公式的寻找，可以说是递归中最难的一步了，递推公式的意义在于逐渐减少算法的规模，或者定义一种方式让输入的值尽可能地靠近临界值，也就是找一个关系f(n) 与 f(n-x)序列的关系，f(n) 代表要解决的问题规模，f(n-x) 比n小的问题规模的函数值，这是递归函数中的关键一步，没有递推公式，就没有递归。

递归案例

1. 斐波那契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34….，即 第一项 f(1) = 1, 第二项 f(2) = 1, 第三项 f(3) = 3, ….., 第n项 f(n) = f(n-1) + f(n-2) 也就是第n项，为前两项的和，递归实现求第 n 项的值是多少。

1. 第一步：考虑递归函数的基本要素，参数，返回值，函数体

函数F(n)的功能是求斐波那契数列第n项的值为多少，入参为n，返回值为第n项的值

public int F(int n) {
}

1. 第二步，递归边界

当边界值n = 1, 2 时， F(n) = 1，这里n的取值范围为n>=1。
边界值

public int F(int n) {
    if(n <= 2) return 1;
}

1. 第三步：寻找递推公式，找出函数的等价关系

根据斐波那契数列的特征很容易推断出，第n项的值为前两项值的和，因此等价关系为F(n) = F(n-1) + F(n-2) 完善代码如下。

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

2. 青蛙台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1. 第一步：考虑递归函数的基本要素，参数，返回值，函数体

函数F(n)的功能是求n级台阶，小青蛙总共有几种跳法，入参为台阶级数n，返回值为跳法的种类

public int F(int n) {
}

1. 第二步，递归边界

当边界值n = 1， F(n) = 1，这里n的取值范围为n>=1。
边界值

public int F(int n) {
    if(n <= 1) return 1;
}

1. 第三步：寻找递推公式，找出函数的等价关系

对于数据信息，根据斐波那契数列的特征很容易推断出，第n项的值为前两项值的和，因此等价关系为
F(n) = F(n-1) + F(n-2) 完善代码如下。

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