08. 算法之递归算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了08. 算法之递归算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

递归，字面意思是递出去，拿回来，通过不断递过去，拿回来的过程，将每次调用结果保存起来，最后实现循环调用。递归在某些情况下会极大降低我们编程的复杂度。是软件开发工程师一定要掌握的技能。

1. 概念

递归：在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。
08. 算法之递归算法

2. 本质

递归，去的过程叫"递"，回来的过程叫”归“。递是调用，归是结束后回来。是一种循环，而且在循环中执行的就是调用自己。递归调用将每次返回的结果存在栈帧中

2.1 递归三要素

递归结束条件
函数的功能，这个函数要干什么
函数等价公式，递归公式，一般是每次执行之间，或者个数之间逻辑关系

3. 小例子

3.1 循环实现

@Test
public void test1(){
    for (int i = 0; i < 5; i++) {
        System.out.println("你好呀");
    }
}

3.2 递归实现

void print(int count,String msg){
    //结束条件
    if (count<=0){
        return;
    }
    //函数功能
    System.out.println(msg);
    //等价公式
    print(--count,msg);
}

@Test
public void test2(){
    print(5,"你好呀");
}

4. 经典案例

4.1 斐波那契数列

0、1、1、2、3、5、8、13、21、34、55…

4.2 规律：

从第3个数开始，每个数等于前面两个数的和

4.3 递归分析

函数功能：返回n的前两个数之和
结束条件：从第三个数开始，n<=2
等价公式：fun(n)=fun(n-1)+fun(n-2)

4.4 代码实现

@Test
public void test3(){
    int febnum = febnum(10);
    System.out.println(febnum);
}

int febnum(int n){
    if (n<0){
        System.out.println("输入错误");
    }
    //结束条件
    if (n==0 || n==1){
        return n;
    }
    //等价公式 函数功能
    return febnum(n-1)+febnum(n-2);
}

5. 时间复杂度

斐波那契数列普通递归解法为O(2^n)

6. 优缺点

6.1 优点：

代码简单

6.2 缺点：

占用空间较大，如果递归太深，可能会发生栈溢出，可能会有重复计算通过备忘录或递归的方式去优化（动态规划）

7. 应用

递归作为基础算法，应用非常广泛，比如在二分查找、快速排序、归并排序、树的遍历上都有使用递归回溯算法、分治算法、动态规划中也大量使用递归算法实现。

8. 斐波那契优化

通过上面的算法可以看到，我们实际做了大量的重复计算，比如计算f（5）需要计算f(4) 和 f(3),但是在计算f(4)的时候，又需要计算f(3)和f(2),又因为这是层层递归的，数字一大，递归的层数，计算的次数就会迅速扩张。为此，我们可以优化一下处理逻辑

8.1 动态规划

8.1.1 逻辑分析

斐波那契数的边界条件是 F(0) = 0 和 F(1) = 1当 >1 时，每一项的和都等于前两项的和，因此有如下递推关系:
F(n)= F(n -1) + F(n - 2)
由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系边界条件为 F(0) 和 F(1)。根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n)的实现。
由于 F(n)只和F(n - 1)与 F( - 2)有关，因此可以使用滚动组思想] 把空间复杂度优化成 0(1)。

8.1.2 代码验证

public int fib(int n) {
	//因为数会很大，为此对结果取模，保证最终计算结果不会太大
    static final int MOD = 1000000007;

    if (n < 2) {
        return n;
    }
    int p = 0, q = 0, r = 1;
    for (int i = 2; i <= n; ++i) {
        p = q;
        q = r;
        r = (p + q)%MOD;
    }
    return r;
}

8.1.3 复杂度分析

时间复杂度为O(n)
空间复杂度为O(1)

8.2 矩阵快速幂

8.2.1 前置知识

如需求数据 a 的幂次，此处 a 可以为数也可以为矩阵，常规做法需要对a进行不断的乘积即 a * a * a * … 此处的时间复杂度将为 O(n)
以3^10为例

3^10=3*3*3*3*3*3*3*3*3*3

    =9^5 = 9^4*9

    =81^2*9

    =6561*9

基于以上原理，我们在计算一个数的多次幂时，可以先判断其幂次的奇偶性，然后：
如果幂次为偶直接 base(底数) 作平方，power(幂次) 除以2
如果幂次为奇则底数平方，幂次整除于2然后再多乘一次底数
对于以上涉及到 [判断奇偶性] 和 [除以2] 这样的操作。使用系统的位运算比普通运算的效率是高的，因此可以进一步优化：把 power % 2 == 1 变为 (power & 1) == 1。把 power = power / 2 变为 power = power >> 1

8.2.2 逻辑分析

08. 算法之递归算法

8.2.3 代码验证

package org.wanlong.recursion;

class Solution {
    public int fib(int n) {
        //矩阵快速幂
        if (n < 2) {
            return n;
        }
        //定义乘积底数
        int[][] base = {{1, 1}, {1, 0}};
        //定义幂次
        int power = n - 1;
        int[][] ans = calc(base, power);
        //按照公式，返回的是两行一列矩阵的第一个数
        return ans[0][0];
    }

    //定义函数,求底数为 base 幂次为 power 的结果
    public int[][] calc(int[][] base, int power) {
        //定义变量，存储计算结果，此次定义为单位阵
        int[][] res = {{1, 0}, {0, 1}};

        //可以一直对幂次进行整除
        while (power > 0) {
            //1.若为奇数，需多乘一次 base
            //2.若power除到1，乘积后得到res
            //此处使用位运算在于效率高
            if ((power & 1) == 1) {
                res = mul(res, base);
            }
            //不管幂次是奇还是偶，整除的结果是一样的如 5/2 和 4/2
            //此处使用位运算在于效率高
            power = power >> 1;
            base = mul(base, base);
        }
        return res;
    }

    //定义函数,求二维矩阵：两矩阵 a, b 的乘积
    public int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                //矩阵乘积对应关系
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

8.2.4 复杂度分析

时间复杂度 O(logn)
空间复杂度O(1)

8.3 备忘录

8.3.1 逻辑分析

前面提到计算复杂度高很大原因是重复计算，为此，很容易想到的是，我们将计算结果保存起来，下次先看看有没有计算过，如果计算过，就不重复计算了

8.3.2 代码验证

package org.wanlong.recursion;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wanlong
 * @version 1.0
 * @description:
 * @date 2023/5/30 11:02
 */
public class SolutionWithMap {

    Map<Integer, Integer> result = new HashMap<>();

    int febnum(int n) {
        if (n < 0) {
            System.out.println("输入错误");
        }
        //结束条件
        if (n == 0 || n == 1) {
            return n;
        }
        //判断是否计算过
        if (result.get(n) != null) {
            return result.get(n);
        }
        int febnum1 = febnum(n - 1);
        int febnum2 = febnum(n - 2);
        result.put(n - 1, febnum1);
        result.put(n - 2, febnum2);
        //等价公式 函数功能
        int res = febnum1 + febnum2;
        result.put(n, res);
        return res;
    }


}

测试类验证

 //测试备忘录
 @Test
 public void test6(){
     int fib = new SolutionWithMap().febnum(10);
     System.out.println(fib);
 }

8.3.3 复杂度分析

时间复杂度O(n^2)
空间复杂度O(n)

以上，本人菜鸟一枚，如有错误，请不吝指正。文章来源地址https://www.toymoban.com/news/detail-464534.html

到了这里，关于08. 算法之递归算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！